Bipartite Graph Check

Problem

Return True if the undirected graph can be coloured with two colours so that every edge joins different colours, and False otherwise.

Run BFS from every unvisited node, assigning the opposite colour to each neighbour and failing on any conflict. An empty graph is bipartite, and the graph may be disconnected.

Hint

A graph is bipartite exactly when it has no odd-length cycle.

Test cases

case 1

in: [[[1,2,3],[0,2],[0,1,3],[0,2]]]

expected: false

case 2

in: [[[1,3],[0,2],[1,3],[0,2]]]

expected: true

case 3

in: [[]]

expected: true

case 4

in: [[[]]]

expected: true

case 5

in: [[[1],[0]]]

expected: true

Starter codePython

def is_bipartite(graph):
    # Your code here
    pass

5 test cases · run your code against them in the editor