mathschallenge.net logo

Euler Rules

Problem

A connected graph is said to be planar if it is possible to be drawn with no intersecting edges.

If V represents the number of vertices, E the number of edges, and R the number of regions, it can be verified that the Euler's rule, V + R = E + 2, holds for the two graphs below (the regions are indicated by the numbers on the graphs).


For the graph on the left: V = 3, R = 2, E = 3, so V + R = E + 2 =5.
For the graph on the right: V = 5, R = 4, E = 7, so V + R = E + 2 = 9.

Prove that Euler's rule is true for all planar graphs.


Solution

This simple rule can be proved easily by induction. Consider the following diagrams.


Suppose that diagram 1 represents part of a planar graph for which Euler's rule holds; that is, V + R = E + 2.

By adding one vertex and one edge (diagram 2), we increase both sides of the equation by 1, so the formula remains true.

By adding one extra edge (diagram 3), we introduce one extra region, thus both sides of the equation increase by 1 once more, and the formula still holds.

As it is clearly true for one vertex (V = 1, E = 0, R = 1), it has been proved, inductively, to be true for all planar graphs.

If V represents the number of vertices, E the number of edges, and F the number of faces, prove that Euler's rule, V + F = E + 2, holds for the Platonic solids.
Explain how it is still true for a cylinder.
For which type of polyhedra does it not work?

Problem ID: 242 (16 Oct 2005)     Difficulty: 4 Star

Only Show Problem