Recipe

Test a graph for bipartiteness

Use when: you're given a graph and asked whether it can be properly colored with only two colors

Goal: a genuine two-coloring if one exists, or a specific odd cycle proving that none can

Taught in Bipartite graphs and 2-colorability, revisited

Quick recipe

Root and color, then BFS outward by distance parity
Check every edge, not only the ones BFS's tree used
Read the verdict off whether a conflict turned up

1
Choose any vertex as the root and color it 1. Then explore outward with breadth-first search, coloring each newly reached vertex the opposite color of the vertex that just reached it.

Example

In the 5-cycle $v_1\text{-}v_2\text{-}v_3\text{-}v_4\text{-}v_5\text{-}v_1$ , root at $v_1$ (color $1$ ). BFS distances come out $v_2{:}1$ , $v_5{:}1$ , $v_3{:}2$ , $v_4{:}2$ , giving colors $v_1{=}1,\ v_2{=}2,\ v_5{=}2,\ v_3{=}1,\ v_4{=}1$ .

Why: two vertices sitting at the same distance parity from the root are forced to the same color by this rule, and that's exactly what a genuine two-part split would also require if one exists.
2
Go through the complete edge list, including any edge the BFS spanning tree skipped over, and confirm each one joins two different colors.

Example

Checking every edge of $C_5$ : $v_1v_2$ ( $1$ , $2$ ) fine, $v_2v_3$ ( $2$ , $1$ ) fine, $v_3v_4$ ( $1$ , $1$ ) a conflict. $v_4v_5$ ( $1$ , $2$ ) and $v_5v_1$ ( $2$ , $1$ ) are both fine. One conflict turns up, on edge $v_3v_4$ .

⚡ Shortcut

If an odd cycle is visible by eye before doing any layering at all, a triangle or a 5-cycle, say, the graph is already known to be non-bipartite. Naming that cycle settles it; no coloring attempt is required first.

Why: a coloring failure always shows up as a same-color edge somewhere, so skipping the edges the tree never used could hide exactly the one edge that matters.
3
Once every edge has been checked, the presence or absence of a same-color conflict alone decides the answer, with no further work needed.

Example

The conflicting edge $v_3v_4$ , together with the two BFS branches back to root $v_1$ ( $v_1v_2v_3$ and $v_1v_5v_4$ ), traces out the odd cycle $v_1v_2v_3v_4v_5v_1$ : the whole 5-cycle is its own certificate.
- no edge joins two same-colored vertices — the graph is bipartite, with the even-distance and odd-distance vertices as the two parts.
- at least one edge joins two same-colored vertices — the graph is not bipartite, and that edge closes an odd cycle back through the root.
Why: König's theorem guarantees these are the only two possible outcomes, so checking every edge once is always enough to decide between them.

Common mistakes

Checking only the edges the BFS tree used to discover new vertices, and skipping chords or cross edges that never played that role.
Assuming a graph "looks" too tangled to be bipartite instead of actually running the odd-cycle test on it.
Declaring victory after a few edges check out, instead of confirming every single edge in the graph.
Trying to patch one conflicting edge by flipping a single vertex's color, instead of recognizing that no two-coloring of the whole graph works.