Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Test whether a graph is bipartite

Use when: you're given a graph, drawn or listed by edges, and asked whether it splits into two sides with every edge crossing between them

Goal: a definite classification, backed by either a working two-coloring or the odd cycle that blocks one

Taught in Review: bipartite graphs and matchings

Quick recipe

  1. Pick a start vertex and color it
  2. Color every neighbor the opposite color, and keep walking outward
  3. Read the result once every reachable vertex is colored (or a conflict appears)
  1. 1

    Choose any vertex in the graph and assign it color 1. This is the seed every other color gets built from.

    Example

    On the 6-cycle a-b-c-d-e-f-a from the widget above, start at a and color it 1.

    Why: the two colors will stand for the graph's two sides, so one vertex has to anchor which side is which before anything else can be assigned.

  2. 2

    For each vertex you've just colored, assign the opposite color to every uncolored neighbor across each edge, working outward across the whole graph.

    Example

    Continuing from a=1: b=2 (neighbor of a), c=1 (neighbor of b), d=2, e=1, f=2. Check the closing edge f-a: f=2 and a=1 differ, so no conflict.

    • a neighbor is uncolored — assign it the opposite color and continue
    • a neighbor is already colored the same as the vertex you're extending from — stop, this edge is a conflict

    ⚡ Shortcut

    If the graph is literally a single cycle, skip the coloring walk entirely: just count the cycle's edges. An even count always colors cleanly; an odd count is guaranteed to conflict exactly once, at the closing edge, matching the odd-cycle rule directly.

    Why: an edge joining two same-colored vertices would put both its endpoints on the same side, exactly what a bipartite split forbids.

  3. 3

    No conflict after every vertex is colored means the two color classes form a genuine bipartition. A conflict means the graph isn't bipartite, and it exposes an odd cycle.

    Example

    The 6-cycle finishes clean: \{a,c,e\} against \{b,d,f\}. Running the same process on the 5-cycle a-b-c-d-e-a gives a=1,b=2,c=1,d=2,e=1, and the closing edge e-a repeats color 1 on both ends, a conflict confirming what an odd-cycle count already shows.

    • coloring finishes with no conflict — bipartite, with the parts read straight off the two colors
    • a conflict appears — not bipartite, and the vertices colored so far trace out an odd cycle

    Why: the color-conflict test and the odd-cycle test are the same fact seen two ways, since a graph two-colors successfully exactly when it has no odd cycle.

Common mistakes

  • Assuming a graph is bipartite just because no odd cycle jumps out visually, instead of finishing the coloring or finding the conflict explicitly.
  • Coloring a neighbor arbitrarily instead of strictly the opposite color of the vertex being extended from.
  • Checking only part of the graph when it has more than one component; each component needs its own coloring walk.
  • Declaring "not bipartite" from one suspicious-looking edge without actually tracing a full color conflict back to it.