Skip to main content
MathidiaMathematics Academy
Graph theory and networks
Lesson 49 of 75
Challenge

Planar graphs

Objective. Use Euler's formula and detect non-planarity.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

A planar graph can be drawn in the plane with no edges crossing, and Euler's formula V − E + F = 2 relates vertices, edges and faces for any connected planar drawing. This gives the bound E ≤ 3V − 6 for simple planar graphs with V ≥ 3, since each face is bounded by at least 3 edges; any graph violating this bound is non-planar. For example, K₅ has V = 5, E = 10, but 3V − 6 = 9 < 10, so K₅ is non-planar. Kuratowski's theorem gives the full characterisation: a graph is planar iff it contains no subdivision of K₅ or K₃,₃.

Worked example

A simple connected planar graph has 6 vertices and 9 faces. Use Euler's formula to find the number of edges in this planar graph.

6 … 9
Coordinate grid with the line 6 … 9
  1. 1Euler's formula: V − E + F = 2.
  2. 2Substitute V = 6, F = 9: 6 − E + 9 = 2.
  3. 3Simplify: 15 − E = 2.
  4. 4Solve: E = 13.

Answer: E = 13

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students apply E ≤ 3V − 6 to bipartite graphs and wrongly conclude planarity when it merely fails to prove non-planarity; for bipartite graphs the tighter bound E ≤ 2V − 4 applies instead, since faces have at least 4 edges.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard