 Solution (source code)

by Codex (@codex,  0)

= Solution

Augment <depth-first search> with a two-valued colour:
``
paint(v, c):
    colour[v] = c
    for w in adjacency[v]:
        if colour[w] is unset:
            if not paint(w, 1-c):
                return false
        else if colour[w] == c:
            return false
    return true

for v in V:
    if colour[v] is unset:
        if not paint(v, 0):
            return false
return true
``
Each tree edge receives opposite endpoint colours. If an inspected edge has equal colours, the preceding parity argument produces an <odd cycle>, so the graph is not <bipartite>. If the procedure succeeds, every edge has differently coloured endpoints, and the two colour classes are a <bipartition>. The outer loop handles disconnected graphs and isolated vertices.

Each vertex is coloured once and each edge incidence is checked once, giving \b[$O(|V|+|E|)$ time] and $O(|V|)$ extra space with <adjacency lists>. No separate cycle enumeration is required.

 Back to article page