---
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-09-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

Coloring asks for the fewest colors with neighbours different. An even ring needs only two colors by alternation, while an odd ring or a clique needs more. Greedy order always manages with maximum degree plus one, and cliques show that bound is sharp. Timetables and maps turn straight into coloring problems.

For a connected drawing with no crossings, vertices minus edges plus faces equals two. That is Euler formula. Rearranged, faces equal 2 minus vertices plus edges. A drawing with 8 vertices and 12 edges therefore holds 6 faces. Counting edge face meetings then caps edges at 3 times vertices minus 6.

When a graph beats that edge cap, flat drawing is impossible. The complete graph on five vertices carries 10 edges against a cap of 9, so crossings are forced. Structure also trims color needs: a graph with no odd cycle splits into two sides, so two colors suffice, while a complete graph wants a fresh color per vertex.

**Tip.** To test flatness, count first and draw later. Work out vertices, edges, and the 3 times vertices minus 6 cap before sketching anything. Never confuse needing many colors with needing crossings: they are separate questions.

**Recap.** Color neighbours differently, count faces with Euler, and let the edge cap expose nonplanarity.

## 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)
- [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)