Why can a conflict graph be checked for two-colourability in linear time when three-colourability is NP-complete?
answer
- which side of the feasibility line
- colour one vertex, then propagate
- forced consequence versus free choice
- odd cycle is the whole obstruction
- the third colour is what bites
basics
~20 sTwo colours leave no freedom: fix one vertex and propagation forces every other, so one traversal either succeeds or exposes an odd cycle. A third colour restores a choice at each vertex, and those choices interact globally.
solid answer
~40 sWith two colours the problem is not a search at all. Pick any vertex, give it colour A, and every neighbour is forced to B, their neighbours back to A, and so on; a breadth-first traversal propagates this through a whole component in `O(V + E)`. Exactly one thing can go wrong — an edge joining two vertices the traversal has already put in the same class — and that edge closes an odd cycle, the only obstruction to two-colourability. With three colours, fixing a vertex leaves each neighbour two options rather than one, nothing propagates, and the consequence of a choice can surface arbitrarily far away. Deciding three-colourability is NP-complete, and it stays NP-complete even on planar graphs whose vertices have at most four neighbours.
code
pseudocode · 12 linesfor each vertex s with colour unset:
colour[s] = A
queue = [s]
while queue not empty:
v = pop(queue)
for each neighbour u of v:
if colour[u] is unset:
colour[u] = opposite(colour[v])
push(queue, u)
else if colour[u] == colour[v]:
return NOT_TWO_COLOURABLE // this edge closes an odd cycle
return TWO_COLOURABLEgo deeper
Hold the pair the right way round: two colours is a linear traversal, three or more is NP-complete. Being able to say which side a requirement lands on is most of the value here.
Explain the propagation argument — one vertex fixed forces all the rest — and name the odd cycle as the only obstruction. Then say precisely what a third colour changes: a free choice at every vertex that no local rule settles.
Show that you check the colour count before quoting a complexity. Given a scheduling requirement, say which restriction would move it to the easy side, and test that before anyone reaches for heavy machinery.
The judgment is whether to negotiate the requirement rather than solve it. A two-group split with a small exception list is often cheaper to operate than an exact three-group assignment nobody can guarantee in the worst case.
## What the two questions actually ask A **conflict graph** puts one vertex per session and one edge between every pair of sessions that cannot share a room or a slot. A **k-colouring** labels each vertex with one of `k` colours so that no edge joins two vertices carrying the same colour; here a colour is a slot. Two questions then look like the same question with a different number in it: - *Can this programme run in two slots?* - *Can it run in three?* They are not the same question. The first is settled by one traversal of the graph. The second is **NP-complete**, meaning no algorithm is known that settles it in time polynomial in the size of the graph, and finding one would settle every problem in NP at once. The gap has nothing to do with how big the graph is; it is created by the number of colours. ## Two colours: every choice is forced Give any vertex colour A. Every neighbour must then be B, every neighbour of those must be A again, and so on. There is never a moment of choice, so there is nothing to search: - The colour of every vertex in a connected component is determined by the colour of the first vertex, up to swapping the two colour names. - A breadth-first traversal assigns colours by the parity of the level a vertex sits on: even levels A, odd levels B. - Only one thing can go wrong — the traversal meets an edge whose two ends already carry the same colour. Both ends then sit at the same parity from the start vertex, so the edge closes a cycle of **odd** length. - An odd cycle is the *only* obstruction. A graph containing none can always be two-coloured. So a failure is not "my heuristic gave up"; it is a proof of impossibility, and the odd cycle is a short witness you can print. - Total work is `O(V + E)` — one pass, no backtracking, no re-visits. That is the shape of every genuinely easy constraint problem: a local rule that turns a decision into a forced consequence, plus a single clean reason for failure. ## Three colours: the choice comes back Colour a vertex A, and each neighbour now has two admissible colours, B or C. Propagation halts at the very first branch. Worse, the consequences are not local: choosing B here can make a far-away subgraph impossible to finish, and nothing visible at either end says so. The decision is NP-complete, and the hardness survives severe restriction — it remains NP-complete for **planar** graphs in which no vertex has more than four neighbours. So "our conflicts are drawn on a floor plan" and "nothing conflicts with more than four other things" do not rescue the instance. There is also no cheap certificate for a *negative* answer the way an odd cycle certifies the two-colour case. Three-colourability can fail for reasons spread over the whole graph rather than concentrated in one small structure. Two traps worth naming, because both are common: 1. **"No triangles, so three colours are enough."** False. Graphs with no triangle at all can be built that require arbitrarily many colours. 2. **"NP-complete means instances are unsolvable."** No. It is a worst-case statement about a family of inputs; particular instances are often settled instantly. ## Where the line sits | Question about the conflict graph | Cost | What decides it | |---|---|---| | Do two slots suffice? | `O(V + E)` | Parity of cycles, found by one traversal | | Do three slots suffice? | NP-complete | No local characterisation is known | | Does any fixed number of slots above two suffice? | NP-complete | The same branching argument applies | | What is the smallest number of slots? | At least as hard as the decision | Optimising over the same choices | ## Reading it back into the schedule The practical value of this pair is not the algorithm; it is the reflex of asking *how many colours* before quoting a cost. In a requirement that reads "split these into two non-conflicting groups", you can promise an exact answer and a reason when it is impossible. In a requirement that reads "fit these into three rooms", you cannot promise an exact answer in general, and the honest engineering conversation moves to what you do instead — a different subject with its own trade-offs. Getting the two cases the right way round, and saying which one a requirement has landed in, is most of what an interviewer is checking.
- What single structure certifies that a graph cannot be two-coloured, and how does the traversal find it?An odd-length cycle. The traversal gives every vertex a parity relative to its start vertex, and an edge whose two ends share that parity closes a cycle of odd length. Walking the two tree paths back to their common ancestor prints the cycle, so the negative answer arrives with a short checkable witness rather than an exhausted search.
- Is deciding that a graph needs exactly three colours the same problem as deciding that three colours suffice?Not literally, though the two stand or fall together. "Three suffice" is three-colourability. "Exactly three" means three-colourable and not two-colourable, and the second half is the cheap traversal — so the two questions differ by a linear-time test. Interviewers use the distinction to check that you pin down which version of a problem you are classifying.
saying these in an interview costs you the question
- Says graph colouring is NP-complete regardless of how many colours are allowed.
- Claims deciding two colours needs backtracking like the general case does.
- Thinks a graph without triangles can always be coloured with three colours.
- Believes NP-complete means no three-colouring instance is ever settled quickly.
- Blames graph size for the hardness instead of the number of colours allowed.