Exercise 1694Combinatorics › Graph theoryL1Added 3 Nov 2026

Planar graphs and Euler's formula

#planar#Euler formula#faces

Statement

State Euler's formula for connected planar graphs and use it to show that $K_5$ is not planar.

Hint

Euler: $v-e+f=2$ . For $K_5$ , $v=5$ , $e=10$ ; if planar, each face has $\ge3$ edges, so $3f\le 2e$ .

Show solutionHide solution

Solution

Euler's formula. $v-e+f=2$ for connected planar graphs ( $f$ = faces, including the outer face).

$K_5$ . $v=5$ , $e=10$ , so $f=2-5+10=7$ . But each face has $\ge3$ edges (bipartite-like requirement), so $3f\le2e$ , i.e. $21\le20$ , contradiction.

Conclusion. $K_5$ is not planar.

Planar graphs and Euler's formula

Statement

Solution

More problems in Graph theory