DSA Is This Graph Bipartite

The problem

A bipartite graph is a graph whose vertices split into two groups. No edge joins two vertices inside one group.

The input is a graph. The output is True or False. True means such a split exists.

cases = [
    ("path", "A-B-C-D", True),
    ("square", "A-B-C-D-A", True),
    ("triangle", "A-B-C-A", False),
    ("two parts", "A-B and C-D", True),
]
for name, shape, expected in cases:
    print(name, shape, "bipartite:", expected)

A path and a square both split cleanly. A triangle does not. The last case holds two separate pieces, and each piece must split cleanly.

Intuition: colouring without checking the edges

Colouring is a way to build the split. Give one vertex colour 0. Give each neighbour colour 1, then alternate along each edge.

The trap is colouring greedily and never checking. A colouring can look tidy in a list and still break on one edge.

edges = [("A", "B"), ("B", "C"), ("C", "A")]
colour = {"A": 0, "B": 1, "C": 0}
print("colours:", colour)
for u, v in edges:
    print("edge", u, v, "colours", colour[u], colour[v], "same:", colour[u] == colour[v])

The list of colours hides the fault. The edge check finds it. Edge C-A joins two vertices of colour 0.

So the method needs two jobs. It colours new vertices. It also checks every edge between coloured vertices.

Brute force: try every colouring

A brute force tries every assignment of colours. Each vertex gets colour 0 or colour 1. A colouring passes when every edge joins different colours.

The search is complete. If any colouring passes, the graph is bipartite. If none passes, it is not.

import itertools

def brute_bipartite(graph):
    names = sorted(graph)
    tried = 0
    for combo in itertools.product([0, 1], repeat=len(names)):
        tried += 1
        colour = dict(zip(names, combo))
        ok = True
        for v in names:
            for nxt in graph[v]:
                if colour[nxt] == colour[v]:
                    ok = False
        if ok:
            return True, tried
    return False, tried

square = {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}
triangle = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}
print("square:", brute_bipartite(square))
print("triangle:", brute_bipartite(triangle))

Four vertices give sixteen colourings. The square finds a passing one early. The triangle tries all eight of its colourings and finds none.

The cost doubles with each added vertex. Ten vertices already give 1024 colourings. The count, not the clock, shows the problem.

The optimal solution: colour and check in one search

The state is the colour map, which holds the group of each visited vertex. That one sentence carries the method.

Search from each uncoloured vertex. Colour a neighbour with the opposite colour. A neighbour already holding the same colour proves the answer False.

from collections import deque

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

cases = [
    ("path", {"A": ["B"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C"]}),
    ("square", {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}),
    ("triangle", {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}),
    ("two parts", {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"]}),
]
for name, graph in cases:
    print(name, "bipartite:", is_bipartite(graph))

All four cases from section 1 pass. The disconnected case also passes. Its second piece starts fresh with colour 0.

Walkthrough: colouring the square

The square has vertices A, B, C and D. Its edges form a cycle of length four. Watch the colour map grow one step at a time.

from collections import deque

graph = {"A": ["B", "D"], "B": ["A", "C"], "C": ["B", "D"], "D": ["A", "C"]}
colour = {"A": 0}
queue = deque(["A"])
print("start:", colour)
while queue:
    v = queue.popleft()
    for nxt in graph[v]:
        if nxt not in colour:
            colour[nxt] = 1 - colour[v]
            queue.append(nxt)
            print("coloured", nxt, "as", colour[nxt], ":", colour)

A starts at colour 0. Its neighbours B and D take colour 1. Vertex C is reached from B and takes colour 0.

The last edge joins C and D. Their colours are 0 and 1, so there is no clash. The finished map gives the two groups, colours 0 and 1.

Complexity

The search visits each vertex once and checks each edge once, so the time is O(V + E) for V vertices and E edges.

The colour map and the queue hold at most one entry per vertex, so the space is O(V).

from collections import deque

def counted(graph):
    colour = {}
    visits = 0
    checks = 0
    for start in sorted(graph):
        if start in colour:
            continue
        colour[start] = 0
        queue = deque([start])
        while queue:
            v = queue.popleft()
            visits += 1
            for nxt in graph[v]:
                checks += 1
                if nxt not in colour:
                    colour[nxt] = 1 - colour[v]
                    queue.append(nxt)
    return visits, checks

for n in [4, 8, 16]:
    path = {}
    for i in range(n):
        neighbours = []
        if i > 0:
            neighbours.append(i - 1)
        if i < n - 1:
            neighbours.append(i + 1)
        path[i] = neighbours
    visits, checks = counted(path)
    print("vertices", n, "visits:", visits, "edge checks:", checks)

Doubling the vertices doubles both counts. No colouring is ever retried. That steady growth is the gain over the brute force.

Edge cases and pitfalls

An odd cycle is the classic failure. A triangle is the smallest one. Its third edge always joins equal colours.

A disconnected graph is not a failure. Each piece needs its own search start. Skipping later pieces would leave vertices uncoloured and unchecked.

from collections import deque

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

print("empty graph:", is_bipartite({}))
print("one vertex:", is_bipartite({"A": []}))
print("odd cycle:", is_bipartite({"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B"]}))
print("disconnected, one bad piece:", is_bipartite({"A": ["B"], "B": ["A"], "C": ["D", "E"], "D": ["C", "E"], "E": ["C", "D"]}))
print("disconnected, both good:", is_bipartite({"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"]}))

One bad piece settles the whole graph. The search can stop at the first clash. It cannot stop after the first good piece.