--- title: "Graph Colouring and Planarity" description: "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." canonical: https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw source: https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Mathematics · Area: Discrete Mathematics · Ages 21 to 22 Page: https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw ## Ready when they can - 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 ## Lesson: Color maps and test flat drawings 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. *(drawing: The only edges are UV, VW, WX, XY, YZ, ZU. The strip records colours in cycle order, not graph geometry.)* 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. *(drawing: Only colours on already coloured neighbours are blocked at the current vertex.)* 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. *(drawing: Removing one cycle edge merges two faces. The changes to E and F cancel in V - E + F.)* 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. *(drawing: Substitute the face formula into the boundary inequality, then collect the E terms.)* 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. **Recap.** 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.* ## Practice 17 questions on this page, each with its working shown. ## Needs first - [Graphs, Degrees and the Handshake Lemma](https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO) ## Optional connections - [Greedy Choice and the Exchange Argument](https://lightmysky.com/learn/computing/greedy-choice-and-the-exchange-argument-mt_9Fj28VDAV-) - [Euler Trails and Hamilton Cycles](https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt) ## Opens up - [Matchings and Hall's Theorem](https://lightmysky.com/learn/mathematics/matchings-and-halls-theorem-mt_hkWslW5b5U)