COMP2121 Chap.11 Planar Graphs and Graph Colouring
Planar Graphs and Graph Colouring
Planar graphs and Euler's formula
A planar graph can be drawn without crossings, and a connected planar drawing satisfies r equal to e minus v plus 2. Counting region degrees gives the bounds e at most 3v minus 6 and, for triangle-free graphs, e at most 2v minus 4, which prove that the complete graph on five vertices and the complete bipartite graph on three and three are not planar.
Colouring
The chromatic number is the fewest colours that give adjacent vertices different colours.
A clique gives a lower bound, an explicit colouring gives an upper bound, greedy colouring uses at most one more colour than the maximum degree, and every planar graph needs at most four.
Deriving the edge bounds
In a planar drawing of a simple connected graph with at least three vertices, every region is bounded by at least three edges, and each edge borders at most two regions.
So twice the number of edges is at least three times the number of regions.
Substituting Euler's formula gives e at most 3v minus 6. If the graph has no triangles, every region needs at least four edges, and the same argument gives e at most 2v minus 4, which rules out the complete bipartite graph on three and three.
Colouring as a model
Scheduling questions turn into colouring once the vertices, edges and colours are named: exams are vertices, a shared student is an edge, and a time slot is a colour.
The chromatic number is the least number of slots. A clique forces at least as many colours as its size, an odd cycle forces three, and an explicit colouring gives the matching upper bound, which together fix the answer.
What this chapter covers
- 01
Planar drawings
- 02
Euler's formula
- 03
Edge bounds for planar graphs
- 04
Non-planar graphs
- 05
Chromatic number
- 06
Greedy colouring and four colours
Worked example · free
Count regions in a planar drawing
- 2Apply Euler's formula.
- 1Compute the bound 3v minus 6.
- 2Compare and conclude.
Key terms
- Planar graph
- A graph that can be drawn in the plane without edge crossings.
- Chromatic number
- The least number of colours in a proper vertex colouring of a graph.
- Region degree
- The number of edges on the boundary of a region of a planar drawing.
Planar Graphs and Graph Colouring FAQ
Does satisfying the edge bound prove a graph is planar?
No. The bound is necessary but not sufficient. The complete bipartite graph on three and three vertices satisfies it and is still non-planar, which the triangle-free bound shows.
How do I find a chromatic number exactly?
Give a lower bound, usually a clique or an odd cycle, and an explicit colouring with the same number of colours. When the two agree, the chromatic number is known.
What does the four colour theorem say?
Every planar graph can be properly coloured with at most four colours. Some planar graphs need fewer, and non-planar graphs may need more. The theorem is famous for its computer-assisted proof.
Why does an odd cycle need three colours?
With two colours, the colours must alternate around the cycle, which needs an even number of vertices to close up. On an odd cycle the first and last vertices would receive the same colour while being adjacent, so a third colour is required.
What is greedy colouring?
Order the vertices, then give each vertex the smallest colour not used by its already coloured neighbours. Since a vertex has at most the maximum degree of such neighbours, greedy colouring never uses more than the maximum degree plus one colours, though a poor ordering can use more colours than necessary.
Exam move
Practise Euler's formula on small drawings and the two edge bounds on the standard non-planar graphs. For colouring, always produce both halves of the answer, a forcing structure and a colouring. Model one scheduling question from scratch, deciding what the vertices, edges and colours are before drawing anything.
When a colouring question mentions timetables, rooms or frequencies, translate it into a graph before drawing anything. Redraw small graphs to remove crossings, and count regions afterwards to confirm Euler's formula holds in your drawing.
Working through Planar Graphs and Graph Colouring in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Planar Graphs and Graph Colouring question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.