Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Planar graphs and graph colouring

Planar graphs are graphs that can be drawn on a plane without edge crossings; this topic covers planarity tests, Euler's formula and consequences, Kuratowski's theorem, and graph colouring (five-colour theorem and chromatic number of planar graphs).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use planar graphs when designing printed circuit board (PCB) layouts, VLSI routing, network drawings and geographical networks where crossings are costly or impossible. Graph colouring for planar graphs appears in register allocation, channel assignment and scheduling where resources must be assigned without conflict.

Key ideas

Start from first principles and define terms in plain language.

  • Graph: a pair G = (V, E) where V is a finite set of vertices (or nodes) and E is a set of unordered pairs of vertices called edges. (Used throughout.)

  • Simple graph: a graph with no loops (edge from a vertex to itself) and at most one edge between any pair of vertices.

  • Plane graph: a drawing of a graph on the plane so that no two edges intersect except at common end-vertices. A specific drawing satisfying this is called an embedding.

  • Planar graph: a graph that has at least one plane embedding (i.e., it can be drawn on the plane without edge crossings).

  • Face: in a plane graph, a maximal connected region of the plane obtained after embedding; one face is unbounded and is called the outer face.

  • Degree of a vertex (deg(v)): number of edges incident on v (counting parallel edges separately in multigraphs); for simple graphs this is an integer ≥ 0.

  • Degree of a face: number of edges on the boundary of the face; an edge on the boundary counted twice if it appears twice (e.g., a bridge bounding the same face twice).

  • Connected graph: a graph where every vertex can be reached from every other by a path.

  • Subdivision of an edge: replacing an edge (u,v) by two edges (u,w) and (w,v) by inserting a new vertex w on that edge.

  • Homeomorphic graphs: two graphs are homeomorphic if they can be obtained from the same graph by a sequence of edge subdivisions and their inverses.

  • Kuratowski's theorem (exact statement): A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph on two sets of three vertices). Assumption: graphs are finite and undirected.

  • Euler's formula (connected plane graphs): If G is a connected plane graph with v vertices, e edges and f faces, then v − e + f = 2. Assumption: graph is connected and drawn in the plane. More generally, if a plane graph has c connected components, then v − e + f = c + 1.

From Euler's formula and counting arguments we derive standard inequalities used in exams:

  1. Sum of vertex degrees: sum_{v in V} deg(v) = 2e. (Every edge contributes 2 to degree sum.)

  2. Sum of face degrees: sum_{faces} deg(face) = 2e. (Every edge borders two face-sides in a plane embedding.)

  3. For a simple connected planar graph with v ≥ 3 every face has degree at least 3, so 3f ≤ 2e. Combine with Euler's v − e + f = 2 to get: e ≤ 3v − 6. (Assumptions: simple graph, connected, v ≥ 3.)

  4. If the planar simple graph has no cycles of length 3 (triangle-free), then every face has degree ≥ 4, so 4f ≤ 2e and hence e ≤ 2v − 4 for v ≥ 3.

  • Maximal planar graph (triangulation): a planar simple graph to which no edge can be added without destroying planarity. In such graphs every face (including outer face) has degree 3 and e = 3v − 6, and f = 2v − 4.

  • Chromatic number χ(G): the minimum number of colours needed to colour vertices so that adjacent vertices receive different colours.

  • Five-Colour Theorem (exact statement): Every planar graph is 5-colourable. (Classical constructive proof by induction uses that every planar graph has a vertex of degree ≤ 5.)

  • Four-Colour Theorem: Every planar graph is 4-colourable. This is a theorem proved with extensive computer assistance; its full proof is beyond standard exam expectations, but you should know the statement and that it is true.

Where universities ask for derivation: the standard step-by-step derivation is the Euler formula proof (induction on edges or using plane embedding), then deriving e ≤ 3v − 6, then using that to prove K5 nonplanar, and similarly for K3,3 using triangle-free inequality.

If an exam asks for a drawing, describe exactly what to draw: when demonstrating non-planarity of K3,3, draw two disjoint sets of three vertices each in two columns and attempt to draw edges; label vertices on left as a1,a2,a3 and right as b1,b2,b3 and show inevitable crossings, then give inequality proof as rigorous.

Formulas

v - e + f = 2 — v is number of vertices (dimensionless), e is number of edges (dimensionless), f is number of faces (dimensionless); applies to any connected plane graph.

sum_{v in V} deg(v) = 2e — deg(v) is degree of vertex v (dimensionless), e as above; applies to any finite undirected graph.

sum_{faces} deg(face) = 2e — deg(face) is number of edge-sides bounding the face (dimensionless); applies to plane embeddings.

e ≤ 3v - 6 — for a simple connected planar graph with v ≥ 3; symbols as above. Consequently, the average vertex degree is less than 6, so every planar graph has a vertex of degree ≤ 5 (useful in 5-colour proofs).

e ≤ 2v - 4 — for a simple connected planar graph with v ≥ 3 and no triangles (triangle-free).

χ(G) ≤ 5 for any planar graph G — Five-Colour Theorem; χ(G) is chromatic number (dimensionless).

(Units: graph quantities are unitless / dimensionless.)

Worked examples

  1. Prove K5 is nonplanar (exam-style short proof).

    • K5: complete graph on 5 vertices has v = 5, e = 10.
    • For any simple connected planar graph with v ≥ 3, e ≤ 3v − 6.
    • Compute 3v − 6 = 3·5 − 6 = 9. But K5 has e = 10 > 9.
    • Therefore K5 cannot be simple planar. So K5 is nonplanar. (Final answer: K5 is nonplanar.)
  2. Prove K3,3 is nonplanar (exam-style short proof using triangle-free inequality).

    • K3,3 is bipartite with two parts of size 3; it has v = 6 and e = 9.
    • Bipartite graphs contain no odd cycles, so in particular no triangles; so any embedding would be triangle-free.
    • For a simple connected triangle-free planar graph v ≥ 3 we have e ≤ 2v − 4.
    • Compute 2v − 4 = 2·6 − 4 = 8. But e = 9 > 8.
    • Therefore K3,3 is nonplanar. (Final answer: K3,3 is nonplanar.)
  3. Colouring a small planar graph — triangular prism trace (model answer for long question).

    • Describe the graph (draw as you work): Draw two triangles one above the other. Label top triangle vertices A, B, C clockwise; bottom triangle vertices A', B', C' below them, with straight vertical edges A-A', B-B', C-C'. Also include triangle edges A-B, B-C, C-A and A'-B', B'-C', C'-A'. This is the triangular prism; it is planar.
    • Goal: find χ(G) and give a proper colouring.
    • Observation: each triangle needs 3 distinct colours among its vertices, but corresponding vertices across the two triangles are adjacent; however, some colour reuse is possible across triangles.
    • Colouring (step-by-step): Colour A = 1 (Red), B = 2 (Green), C = 3 (Blue). Now A' is adjacent to B' and C' (the bottom triangle) and also adjacent to A. So A' cannot be 1; assign A' = 2 (Green) provided it is not adjacent to B' which we will choose accordingly. Next colour B' — B' is adjacent to A' and C' and to B (which is 2), so B' cannot be 2. Choose B' = 3 (Blue). Finally C' is adjacent to A' (2), B' (3) and C (3), so C' cannot be 2 or 3; choose C' = 1 (Red). Check all edges: vertical edges connect different colours, triangle edges on bottom are 1-2-3 distinct. All adjacent pairs are differently coloured.
    • Conclusion: triangular prism is 3-colourable, so χ(G) = 3. (Final answer: Chromatic number is 3 with colouring A=1,B=2,C=3,A'=2,B'=3,C'=1.)

Notes for graders: show the drawing as described and list assignments with the check that adjacent vertices differ.

Common mistakes

  • Counting faces incorrectly: not counting the outer (unbounded) face as a face.
  • Mistaking a particular drawing with crossings for non-planarity: a graph may be planar even if a particular drawing has crossings — you must prove no possible crossing-free embedding exists (use Kuratowski or inequalities) rather than argue from one bad drawing.
  • Using the 4-colour theorem in a proof without noting it is non-elementary; for exams you can state it but not attempt its proof unless the syllabus expects it.
  • In colouring proofs, failing to check every adjacency after colour assignment, especially when recolouring chains (Kempe chains) in five-colour constructive proofs.

For your exam

Kinds of questions you will see and what full-marks answers include:

  • Definitions: define planar graph, plane graph, face, triangulation, chromatic number — give short, exact definitions and a one-line example.
  • Short proofs: derive Euler's formula for a connected plane graph (expected method: induction on edges or faces). Show the two sums equalities (vertex-degree sum and face-degree sum).
  • Derivations: from Euler's formula derive e ≤ 3v − 6 and the triangle-free bound; show K5 and K3,3 nonplanar as corollaries — include v, e numbers and the inequality calculation.
  • Diagram questions: draw a planar embedding of a small graph or show by diagram why a given embedding fails; label vertices and faces and count f.
  • Colouring questions: prove or demonstrate 5-colourability (sketch constructive inductive proof), or colour a particular planar graph and state χ(G). For full marks, explain base case, inductive step, the existence of a vertex with degree ≤ 5, and how to recolour when all five neighbour colours appear.
  • Long question/theory: state Kuratowski's theorem and explain conceptually how it characterises planarity (no need to prove full theorem unless asked at higher level).

Quick check

  1. State Euler's formula for a connected plane graph.
  2. For a simple planar graph with v = 8, what is the maximum possible number of edges?
  3. Is K4 planar? Give a one-line reason.

Answers: 1) v − e + f = 2. 2) e ≤ 3v − 6 = 3·8 − 6 = 18, so maximum 18 edges. 3) Yes; K4 has v=4, e=6 and can be drawn as a tetrahedron shape, so planar (note: satisfying e ≤ 3v − 6 is a necessary but not sufficient condition for planarity).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?