Exercise 964Combinatorics › Graph theoryL1Added 3 Nov 2026

Euler's formula application

#Euler formula#planar#faces

Statement

A connected planar graph has $v$ vertices and $e$ edges. Show that $e\le3v-6$ for $v\ge3$ .

Hint

Each face has at least $3$ edges; each edge borders $2$ faces.

Show solutionHide solution

Face-edge counting. Each face has $\ge3$ edges; each edge is counted twice: $3f\le2e$ , so $f\le2e/3$ .

Euler. $v-e+f=2$ , so $f=2-v+e$ .

Inequality. $2-v+e\le 2e/3$ , so $6-3v+3e\le2e$ , i.e. $e\le3v-6$ .

Conclusion. For planar graphs with $v\ge3$ , $e\le3v-6$ .