Checking If a Graph Is Bipartite

A graph is bipartite if its nodes can be split into two sets such that every edge goes between the sets and never within one. Equivalently, the graph can be coloured with two colours so that no edge joins two nodes of the same colour.

The check is a breadth first search with two colours. Start any uncoloured node with colour zero, and when you reach a neighbour give it the opposite colour. If you ever find an edge whose two ends already have the same colour, the graph is not bipartite.

The mechanism is that the colouring is forced once you choose the first node's colour. Every path from the start alternates colours, so a node reachable by paths of different parity cannot be coloured consistently. An odd cycle is exactly such a conflict, and an odd cycle makes the graph non-bipartite.

The trade-off to name is that you have to start a fresh search from every uncoloured node, because the graph may be disconnected and each component is coloured independently. Forgetting that outer loop is the classic bug, since a single search only covers one component. The complexity is linear in the number of nodes and edges, and the memory is the colour map plus the queue, so it is cheap. The other detail is that the conflict check has to compare against the already assigned colour of the neighbour, and treating an already coloured neighbour as a conflict is a common mistake that would reject every graph with more than one edge.

Colour the graph with two colours using a breadth first search, and report a conflict as soon as two adjacent nodes end up with the same colour.

from collections import deque


def is_bipartite(graph):
    colour = {}
    for start in graph:
        if start in colour:
            continue
        colour[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbour in graph[node]:
                if neighbour not in colour:
                    colour[neighbour] = 1 - colour[node]
                    queue.append(neighbour)
                elif colour[neighbour] == colour[node]:
                    return False
    return True


print(is_bipartite({"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}))
print(is_bipartite({"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}))

The outputs are True and False. The first graph can be split into the pair A and D on one side and the pair B and C on the other, with every edge crossing between them. The second graph is a triangle, and three nodes cannot be coloured with two colours without an edge joining two of the same colour.

The mechanism is that the colour of a node is forced by the colour of the node that discovered it. The conflict check compares the neighbour's existing colour with the node's own colour, and only a matching pair is a problem, because the neighbour may already have been coloured by a different path that agrees with this one.

The trade-off to name is the outer loop over all the nodes, which is needed because the graph may have several disconnected components and each one has to be coloured independently. The early return on a conflict is safe because a single conflict anywhere in the graph is enough to answer the question. The other point is that the same algorithm answers the two colour problem on a graph where the edges are directed as well, in which case the edges have to be treated as undirected for the colouring to mean anything.