Maths WorkshopMaths problems with full solutions
Exercise 1755Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

Euler characteristic by induction

#induction#Euler characteristic#trees

Statement

Prove that a connected planar graph satisfies V−E+F=2V-E+F=2 by induction on the number of faces.

Hint

Remove an edge on a cycle and reduce FF by 11.

Show solutionHide solution

Solution

Setup. Induct on the number of edges EE.

Base case. A tree has F=1F=1 (only outer face), V−E+1=1V-E+1=1 (since E=V−1E=V-1), so V−E+F=V−(V−1)+1=2V-E+F=V-(V-1)+1=2. ✓

Inductive step. If the graph has a cycle, remove an edge from the cycle: the graph stays connected, EE decreases by 11, and FF decreases by 11 (two faces merge). Both sides of V−E+F=2V-E+F=2 change by −1+1=0-1+1=0, preserving the identity.

Conclusion. V−E+F=2V-E+F=2 for connected planar graphs.