Graph Colouring and Planarity
Colour vertices so that neighbours differ, bound the colours needed, and use Euler's formula to see what a graph drawn without crossings cannot contain.
What a learner can do afterwards
- Bound the chromatic number by the maximum degree and exhibit a graph meeting the bound
- Prove Euler's formula for connected planar graphs
- Use the edge bound from Euler's formula to show a specific graph is not planar
1 · Read
Use the vertices, edges and degrees from the graph-basics lesson. Unless stated otherwise, graphs here are finite, simple and undirected: no loops or parallel edges. A proper vertex colouring gives adjacent vertices different colours. The chromatic number is the fewest colours needed. A loop prevents proper colouring because its vertex would have to differ from itself.
A cycle returns to its start without repeating other vertices. An even cycle needs two colours by alternation. An odd cycle needs three: two-colour alternation clashes at closure; a third colour on the last vertex works. Bipartite means two vertex sets with every edge between the sets. A graph is bipartite exactly when it has no odd cycle. One colour per set gives at most two colours. A nonempty edgeless graph needs only one.
Let Δ be the maximum degree. For greedy colouring, order the vertices and choose the first available colour from a fixed ordered palette. Each vertex has at most Δ earlier neighbours, so at most Δ colours are blocked. A palette of Δ + 1 always leaves a free colour. This is an upper bound. The chosen order may use more colours than the chromatic number.
A complete graph on n vertices joins every pair. It has maximum degree n - 1 and needs n colours, attaining the Δ + 1 bound. Separate components can reuse colours because no edges join them. The graph's chromatic number is the largest component chromatic number.
A planar graph admits a drawing whose edges meet only at shared endpoints. A plane graph is a particular such drawing. Count vertices V, edges E and faces F, including the unbounded outer face. For a connected plane graph, Euler's formula is V - E + F = 2. Rearranging gives F = 2 - V + E, E = V + F - 2, or V = 2 + E - F.
Delete a cycle edge in a connected plane graph. Its endpoints stay joined along the cycle, and two faces merge. E and F each fall by one, preserving V - E + F. Repeat until a tree, a connected graph with no cycles, remains. A tree has E = V - 1: remove a leaf and its edge until one vertex remains; a longest path supplies a leaf. A tree encloses no bounded face, so F = 1. Thus V - E + F = 2 for the tree and the original graph.
Let V >= 3 in a connected simple plane graph. Count edge occurrences around each face, counting a bridge twice on the same boundary. Each edge contributes two sides, so the total is 2E. Every boundary has length at least 3, giving 3F <= 2E. Euler gives 3(2 - V + E) <= 2E, so E <= 3V - 6. Equality holds when every boundary has length 3. Exceeding this cap rules out planarity; passing it does not prove planarity.
For a connected simple bipartite plane graph with V >= 3, each face boundary has even length and at least 4 edge occurrences. Thus 4F <= 2E. Substituting F = 2 - V + E gives E <= 2V - 4. A complete bipartite graph joins every vertex on one side to every vertex on the other, with no edges within a side. Side sizes m and n give mn edges.
Colour neighbours differently, count faces with Euler's formula, and use the edge cap to rule out planarity.
Original lesson, practice questions and flashcards written for this learning dataset.
Original readings, additional exercises and flashcards written for this learning dataset. Contemporary Mathematics and WeBWorK graph-theory records informed the study of mathematical facts and exercise design. No source prose, images or code are reproduced.
More to read
A colouring and a minimum
Work with finite simple undirected graphs. A proper vertex colouring gives different colours to adjacent vertices. Showing one colouring proves an upper bound on the chromatic number. Proving a minimum also needs a reason fewer colours cannot work.
For an even cycle, alternate two colours around the cycle. This gives an upper bound of two. Any edge requires different colours at its ends, giving a lower bound of two. The bounds agree. An odd cycle cannot close with alternating colours: the last vertex clashes with the start. Alternate along all but the last vertex and give that vertex a third colour to obtain a proper colouring.
Greedy colouring processes vertices in a chosen order and assigns the first available colour. If the maximum degree is Δ, at most Δ previously coloured neighbours can restrict a vertex. A palette of Δ + 1 always has a colour left. This guarantees a colouring, but the order can affect how many colours are used.
In a complete graph, every pair of vertices is adjacent. All vertices need different colours, so the Δ + 1 bound is attained. For separate components, colour each component and reuse the palette. The largest component requirement is enough, since no edge joins different components.
Reducing a plane graph to a tree
A plane graph is a drawing with edges meeting only at shared endpoints. Its faces include the unbounded outer region. For a connected plane graph, Euler's formula states V - E + F = 2.
To prove it, choose an edge on a cycle and remove that edge. Its endpoints remain connected along the rest of the cycle. All vertices remain, but the regions on the two sides of the removed edge merge. The new counts are V, E - 1 and F - 1. Substitution shows that V - (E - 1) + (F - 1) equals V - E + F.
Continue until no cycle remains. Connectivity has been preserved, so the remaining graph is a tree. A finite tree with more than one vertex has a leaf: an endpoint of a longest path has no further neighbour outside that path, and an extra neighbour on the path would form a cycle.
Remove a leaf and its incident edge repeatedly. Each removal reduces vertices and edges by one until a single vertex with no edges remains. Thus the tree originally had V - 1 edges. Its drawing has no bounded face, so F = 1.
For that tree, V - E + F is V - (V - 1) + 1 = 2. All earlier cycle-edge deletions preserved this expression. It was therefore 2 in the original drawing too.
Using an edge bound in the right direction
Suppose a connected simple graph with V >= 3 has a plane drawing. Count edge occurrences along every face boundary. Each edge contributes two sides. A bridge is counted twice along the same face boundary, so the total is still 2E.
Every face boundary has at least three edge occurrences. Therefore 3F <= 2E. Insert F = 2 - V + E from Euler's formula and collect terms to obtain E <= 3V - 6. If every face boundary has length three, the inequality is an equality.
A complete graph on six vertices has 6 × 5 / 2 = 15 edges. The simple planar bound allows at most 12. This contradiction rules out a plane drawing.
Bipartite graphs have no odd cycles. Their face boundaries have even length and, under the same assumptions, at least four edge occurrences. This gives 4F <= 2E and then E <= 2V - 4. A complete bipartite graph with side sizes three and four has seven vertices and twelve edges. Its bipartite planar cap is ten, so it is not planar.
These are necessary conditions for planarity. Exceeding a cap proves nonplanarity. Passing a cap does not construct a drawing or prove planarity. The simple-graph restriction matters too: parallel edges can create a face boundary of length two, invalidating the boundary-length argument used here.
2 · Watch
Take it off screen
Where it sits
Learn first
Optional connections
This opens up
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.