Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

The two-colouring pattern

Lesson · 9 min read · Graphs · Pattern: two-colouring

Can the nodes be split into two sides with every edge crossing between them? Colour as you search, and an odd cycle is the only thing that can stop you.

What the pattern is

A graph is bipartite if its nodes can be given one of two colours so that every edge joins different colours. Splitting people who dislike each other into two rooms, scheduling two shifts so that no conflicting tasks share one, checking that a set of "opposite" relations is consistent: all ask whether a graph is bipartite.

The test is a search that colours as it goes. Give the start colour A. Every neighbour of an A node must be B, every neighbour of a B node must be A. The colours are forced, so if an edge ever joins two nodes of the same colour, no colouring exists.

Two-colouring

bipartite(graph)

  1. For each uncoloured node s: colour it A and start a breadth-first (or depth-first) search.
  2. When visiting u, for each neighbour v: if v is uncoloured, give it the opposite colour and queue it; if v has u's colour, return false.
  3. Return true.

Why an odd cycle is the obstacle

Going round a cycle the colours alternate, so a cycle can be coloured exactly when its length is even. A graph is bipartite if and only if it has no cycle of odd length.

01234
Around a five-cycle the colours run A, B, A, B, and the fifth node is joined to both an A and a B.

Breadth-first two-colouring of a bipartite graph.

  1. Step 1 / 5
    012345

    0 is uncoloured: give it colour A and start a breadth-first search.

  2. Step 2 / 5
    012345

    From 0: its uncoloured neighbours 1, 3 get the opposite colour, B.

  3. Step 3 / 5
    012345

    From 1: its uncoloured neighbours 2, 4 get the opposite colour, A.

  4. Step 4 / 5
    012345

    From 2: its uncoloured neighbours 5 get the opposite colour, B.

  5. Step 5 / 5
    012345

    Every edge joins colour A to colour B: the graph is bipartite.

colour Acolour Bconflict

How to recognise it

  • "Split into two groups", "two teams", "two rooms", "no two adjacent with the same", "dislikes".
  • The question is yes or no, or asks for the two groups.
  • A constraint that pairs must be different. (Pairs that must be the same are a components problem: merge them first.)
TimeO(n + m)
SpaceO(n)

One search per component; each node is coloured once.

The problems in this module: