## 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.

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