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