488
Graphs and Trees
example 13
Consider K 5 , the simple, complete graph with five vertices. We will try to construct
K 5 with no intersecting arcs by starting with some of the arcs and then adding as
many new arcs as possible without crossing existing arcs. We’ll first lay out five
vertices and connect them as shown in Figure 6.21a. (Because all the vertices in K n
are symmetric, it doesn’t matter how we label them.)
(c)
1
2
5
4
3
(b)
1
2
5
4
3
(a)
1
2
5
4
3
Figure 6.21
Next we connect 1 to 3 and 1 to 4, as shown in Figure 6.21b. Now 2 must be connected to both 4 and 5. This can be accomplished while still preserving the planarity of the
graph by putting these new arcs on the outside, as in Figure 6.21c. The final connection is between nodes 3 and 5. But there is no way to draw an arc from node 3 to node
5 without crossing either the 2-4 arc or one or more of the interior arcs, such as 1-4.
We did have a choice of how to place arcs 1-3 and 1-4; we made them interior
arcs. We could explore whether making these arcs exterior would change anything,
but it turns out that it does not (see Practice 11). Thus it appears that K 5 is not a planar graph. However, we’d still like a proof of this with a firmer foundation—this
sounds too much like an “I can’t do it so it can’t be done” argument. Such a proof
will be given shortly.
praCTiCe 11 Show that adding arcs 1-3 and 1-4 as exterior arcs when constructing K 5 still leads to a
situation where arcs must intersect.
■
praCTiCe 12 Present a construction-type argument that K 3,3 is not a planar graph.
■
One fact about planar graphs was discovered by the eighteenth-century Swiss
mathematician Leonhard Euler (pronounced “oiler”). A simple, connected, planar
graph (when drawn in its planar representation, with no arcs crossing) divides the
plane into a number of regions, including totally enclosed regions and one infinite
exterior region. Euler observed a relationship between the number n of nodes, the
number a of arcs, and the number r of regions in such a graph. This relationship is
known as euler’s formula:
n − a + r = 2
(1)
praCTiCe 13 Verify Euler’s formula for the simple, connected, planar graph in Figure 6.18b.
■
To prove Euler’s formula, we will do a proof by induction on a, the number of arcs.
In the base case, a = 0 and the graph consists of a single node; the only region is the
exterior region (Figure 6.22a). Here n = 1, a = 0, and r = 1, and Equation (1) holds.
Graphs and Trees
example 13
Consider K 5 , the simple, complete graph with five vertices. We will try to construct
K 5 with no intersecting arcs by starting with some of the arcs and then adding as
many new arcs as possible without crossing existing arcs. We’ll first lay out five
vertices and connect them as shown in Figure 6.21a. (Because all the vertices in K n
are symmetric, it doesn’t matter how we label them.)
(c)
1
2
5
4
3
(b)
1
2
5
4
3
(a)
1
2
5
4
3
Figure 6.21
Next we connect 1 to 3 and 1 to 4, as shown in Figure 6.21b. Now 2 must be connected to both 4 and 5. This can be accomplished while still preserving the planarity of the
graph by putting these new arcs on the outside, as in Figure 6.21c. The final connection is between nodes 3 and 5. But there is no way to draw an arc from node 3 to node
5 without crossing either the 2-4 arc or one or more of the interior arcs, such as 1-4.
We did have a choice of how to place arcs 1-3 and 1-4; we made them interior
arcs. We could explore whether making these arcs exterior would change anything,
but it turns out that it does not (see Practice 11). Thus it appears that K 5 is not a planar graph. However, we’d still like a proof of this with a firmer foundation—this
sounds too much like an “I can’t do it so it can’t be done” argument. Such a proof
will be given shortly.
praCTiCe 11 Show that adding arcs 1-3 and 1-4 as exterior arcs when constructing K 5 still leads to a
situation where arcs must intersect.
■
praCTiCe 12 Present a construction-type argument that K 3,3 is not a planar graph.
■
One fact about planar graphs was discovered by the eighteenth-century Swiss
mathematician Leonhard Euler (pronounced “oiler”). A simple, connected, planar
graph (when drawn in its planar representation, with no arcs crossing) divides the
plane into a number of regions, including totally enclosed regions and one infinite
exterior region. Euler observed a relationship between the number n of nodes, the
number a of arcs, and the number r of regions in such a graph. This relationship is
known as euler’s formula:
n − a + r = 2
(1)
praCTiCe 13 Verify Euler’s formula for the simple, connected, planar graph in Figure 6.18b.
■
To prove Euler’s formula, we will do a proof by induction on a, the number of arcs.
In the base case, a = 0 and the graph consists of a single node; the only region is the
exterior region (Figure 6.22a). Here n = 1, a = 0, and r = 1, and Equation (1) holds.