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 by induction on the number of faces.
Hint
Remove an edge on a cycle and reduce by .
Show solutionHide solution
Solution
Setup. Induct on the number of edges .
Base case. A tree has (only outer face), (since ), so . ✓
Inductive step. If the graph has a cycle, remove an edge from the cycle: the graph stays connected, decreases by , and decreases by (two faces merge). Both sides of change by , preserving the identity.
Conclusion. for connected planar graphs.