Section 6.1 Graphs and Their Representations
489
Now assume that the formula holds for the planar representation of any simple, connected, planar graph with k arcs, and consider such a graph with k + 1 arcs. As usual,
we must somehow relate the “k + 1 instance” to a “k instance” so that we can make use
of the inductive hypothesis. Here we consider two cases for the graph with k + 1 arcs.
(b)
(c)
(a)
Figure 6.22
Case 1. The graph has a node of degree 1. Temporarily erasing this node and its
connecting arc (Figure 6.22b) leaves a simple, connected, planar graph with k
arcs, some number n of nodes, and some number r of regions for which (by the
inductive hypothesis)
n − k + r = 2
In the original graph, there was one more arc and one more node but the same
number of regions, so the appropriate formula is
(n + 1) − (k + 1) + r = 2
which, by the inductive hypothesis, is true.
Case 2. The graph has no nodes of degree 1. Then temporarily erase one arc that
helps define an enclosed region (Figure 6.22c). (If no arcs help define an enclosed
region, the graph is a chain and there is a node of degree 1.) This leaves a simple,
connected, planar graph with k arcs, some number n of nodes, and some number r
of regions for which (by the inductive hypothesis)
n − k + r = 2
n the original graph, there was one more arc and one more region, but the same
number of nodes, so the appropriate formula is
n − (k + 1) + (r + 1) = 2
which, by the inductive hypothesis, is true.
praCTiCe 14 In the proof of Euler’s formula, explain why in case 2 the arc to be erased must help define
an enclosed region. Give two reasons.
■
There are two consequences of Euler’s formula if we place further restrictions on
the graph. Suppose we require that the graph not only be simple, connected, and planar but also have at least three nodes. In a planar representation of such a graph, we
489
Now assume that the formula holds for the planar representation of any simple, connected, planar graph with k arcs, and consider such a graph with k + 1 arcs. As usual,
we must somehow relate the “k + 1 instance” to a “k instance” so that we can make use
of the inductive hypothesis. Here we consider two cases for the graph with k + 1 arcs.
(b)
(c)
(a)
Figure 6.22
Case 1. The graph has a node of degree 1. Temporarily erasing this node and its
connecting arc (Figure 6.22b) leaves a simple, connected, planar graph with k
arcs, some number n of nodes, and some number r of regions for which (by the
inductive hypothesis)
n − k + r = 2
In the original graph, there was one more arc and one more node but the same
number of regions, so the appropriate formula is
(n + 1) − (k + 1) + r = 2
which, by the inductive hypothesis, is true.
Case 2. The graph has no nodes of degree 1. Then temporarily erase one arc that
helps define an enclosed region (Figure 6.22c). (If no arcs help define an enclosed
region, the graph is a chain and there is a node of degree 1.) This leaves a simple,
connected, planar graph with k arcs, some number n of nodes, and some number r
of regions for which (by the inductive hypothesis)
n − k + r = 2
n the original graph, there was one more arc and one more region, but the same
number of nodes, so the appropriate formula is
n − (k + 1) + (r + 1) = 2
which, by the inductive hypothesis, is true.
praCTiCe 14 In the proof of Euler’s formula, explain why in case 2 the arc to be erased must help define
an enclosed region. Give two reasons.
■
There are two consequences of Euler’s formula if we place further restrictions on
the graph. Suppose we require that the graph not only be simple, connected, and planar but also have at least three nodes. In a planar representation of such a graph, we