STEP 15 · GRAPHS · THE COLOURING IS FORCED · MEDIUM

Is Graph Bipartite?

WHAT IT SAYS

Decide whether a graph's vertices can be split into two groups such that every edge crosses between the groups.

WHAT IT'S REALLY ASKING

"Colour any vertex red, and you have no further choices: every neighbour MUST be blue, their neighbours MUST be red, outward forever. The propagation either completes — a valid split, found — or two forced colours collide on one vertex, and that collision isn't bad luck, it's a proof: an odd cycle, which no colouring anywhere could ever satisfy. Zero choices means one pass decides."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Try the assignments

Exponential as framed — backtracking explores a choice tree that shouldn't exist

Search over ways to place vertices into two groups — assign greedily with backtracking on conflict, or in the worst framing, test the 2^V possible splits against the all-edges-cross condition.

WHERE THE WORK IS WASTED — Backtracking is machinery for problems WITH choices — where an early decision can be wrong in a way only later context reveals, so alternatives must be held open. Bipartition has no such structure: within one connected piece, the first vertex's colour determines every other vertex's colour by pure implication along edges (and the two global options — swap all colours — are mirror images, succeeding or failing together). A search tree over forced moves is a tree with one real branch; every 'alternative' the backtracker dutifully explores is either identical-by-symmetry or already-refuted. The exponential cost is the price of not noticing there was nothing to decide.

KEY OBSERVATION — THE UNLOCKlink

Propagation with no choices; contradiction equals odd cycle.

The chain of forcing: an edge's endpoints must differ, and with two colours 'differ' means 'determined' — a red vertex makes every neighbour blue, not 'blue or something else'. So within a connected component, seed any vertex with either colour and BFS/DFS the implications outward: each newly reached vertex receives the opposite of its discoverer's colour, no alternatives, no backtracking, ever. Two outcomes exhaust the possibilities. Outcome one: propagation completes with no edge violated — the colouring in hand IS a valid bipartition, constructed rather than searched for. (Each component seeds independently; its two mirror colourings are interchangeable, so seeding arbitrarily loses nothing. The disconnected sweep matters: one odd component anywhere poisons the whole answer.) Outcome two: some edge's endpoints hold the SAME colour. This is not a dead end to back out of — it is a certificate of impossibility, and here is the argument. In BFS layering, a vertex's colour is the parity of its distance from the seed. An edge joining two same-coloured vertices joins two vertices of equal distance-parity; the path from one to the seed, the path from the seed to the other, plus the offending edge, close a cycle of odd total length. And an odd cycle defeats EVERY possible 2-colouring, not just this one: walking any cycle, colours must alternate, and alternation around an odd length returns to the start demanding a colour different from itself — contradiction independent of all choices. So bipartite ⟺ no odd cycle, and the greedy propagation is simultaneously the constructor (even case) and the impossibility-prover (odd case). That dual role is the lesson: when every constraint is an equality/inequality between exactly two items over a two-value domain, assignments propagate deterministically, and a single traversal either builds the answer or exhibits the obstruction. Search is for problems with slack; this one has none.

Colour by BFS parity, per component, verdict on conflict

O(V + E) time — each edge examined once per direction — O(V) colour array

colour[] initialised to uncoloured. For each uncoloured vertex: seed it with colour 0 and BFS; for each edge scanned, an uncoloured neighbour gets the flipped colour and enqueues, a coloured neighbour matching the current vertex's colour returns false immediately. Survive all components: return true. (DFS identical; union-find alternative: union each vertex with all its neighbours' OTHER endpoints... the standard trick unions v's neighbours together and checks v never joins them.)

WHAT YOU TRADED — The forced-propagation insight is rented from the two-colour domain: with k colours (general graph colouring) neighbours constrain but don't determine, choices return, and the problem jumps to NP-hard — the cliff between k=2 and k=3 is the whole story of why this check is linear. The transferable lesson: count the real degrees of freedom before reaching for search — constraints that DETERMINE rather than RESTRICT collapse search into propagation, and any contradiction met along the way is a reusable impossibility certificate, not a backtrack signal.

WATCH THE IDEA RUN

free choices made exactly 1 (the first node)

verdict consistent so far

Bipartite means two-colourable. It sounds like a search over colourings — but you never get to CHOOSE a colour after the first one.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Forced Propagation or Certified Impossibility

YOU'LL SEE IT AGAIN WHEN

Binary labels with 'endpoints must differ' constraints — each assignment DETERMINES its neighbours, leaving zero genuine choices per component.
A conflict during propagation is a structural certificate (odd cycle) refuting ALL assignments, not a wrong turn to undo.
The same traversal doubles as constructor and refuter — build the labelling until it completes or exhibits the obstruction.

SAME BLUEPRINT, DIFFERENT PROBLEM

Possible Bipartition (dislike pairs as edges, verbatim)Detect Cycle in an Undirected Graph (parity is what's new here)Two-colourable regions / Odd cycle detectionUnion-Find with parity (the incremental variant)

The bar isn't "solved it once." It's "could rebuild it from the observation."