Introduction to Graph Theory (19 page)

Figure 80

Figure 81

Figure 82

Figure 83

Figure 84

3) The graph of
Figure 85
is both a supergraph of an expansion of
UG
and a supergraph of an expansion of
K
₅
. For the sake of example I'll extract an expansion of
K
₅
. The first thing I notice is that the graph is nearly symmetric, so it probably won't matter which five vertices I select to call “#1”, “#2”, “#3”, “#4”, and “#5”. But to be safe I'll make sure I include the two (
A
and
D
) having a higher degree than the others. So without further ado I'll let
G
be “#1”,
A
be “#2”,
B
be “#3”,
C
be “#4”, and
D
be “#5”. #1 is joined directly to #2 and #3, so I'll mark these two edges with a jagged line; I'll return later to devise paths from #1 to #4 and #5. #2 is joined directly to #3, #4, and #5, so I'll mark these edges; #3 is joined directly to #4 and #5, so I'll mark these edges; and #4 is joined directly to #5, so I'll mark that edge. Now I can see what material is left for the construction of paths from #1 to #4 and from #1 to #5. I see that I can go from #1 to #4 via
E
, so I'll mark that path. I can't go from #1 to #5 via
F
and
E
, for such a path would have vertex
E
in common with the last path, and the marked subgraph would not be an expansion of
K
₅
; but I see another way of going from #1 to #5, a way that uses only
F
, so I'll choose and mark that path. The marked paths are displayed in
Figure 86
. Now I'll erase everything I haven't marked, leaving the subgraph drawn in
Figure 87a
. This subgraph is isomorphic to the graph of
Figure 87b
; as this last is obviously an expansion of
K
₅
, I'm finished.

Figure 85

Figure 86

Figure 87

Exercises

  
1
.
  
Prove the following statements:

a)
  
If three edges are added to the graph of
Figure 63a
, then at least two of the new edges will be adjacent
.

b)
  
Every graph with v = 5 and
e
= 3 has at least two adjacent edges
.

c)
  
If
v
is an odd number then every graph with
v
vertices and (1/2)(
v
+ 1) edges has at least two adjacent edges.

2.
  
Prove that in
Figure 58
, graph a) is planar, and that graphs b) and c) are nonplanar.

3.
  
The expansions of
K
₃
are the cyclic graphs
C
₃
,
C
₄
,
C
₅
, etc. Satisfy yourself that except for
C
₃
(which is isomorphic to
K
₃
), no cyclic graph is a supergraph of
K
₃
. Thus
K
₃
has the property that none of its expansions (except itself) is also a supergraph. Find a simple graph having the “reverse” property; that is, find a graph
G
such that
every
expansion of
G
is also a supergraph of
G
.

  
4
.
  
Find a planar graph with
v
= 8 whose complement is also planar.

5.
  
It is a fact that every planar graph with
v =
9 has a nonplanar complement. Verify this in one case by drawing a planar graph with v = 9 (make it complicated or the exercise will be boring) and proving that its complement is nonplanar.

6.
  
Draw a nonplanar graph whose complement is nonplanar.

7.
  
Prove that the “Petersen graph” of
Figure 88
is nonplanar.

Figure 88

8.
  
Of the 34 graphs with
v
= 5,
K
₅
is of course the only one that is nonplanar. But of the 156 graphs with
v
= 6, 13 are nonplanar besides
UG
. Find them.

9.
  
Prove: if
H
is an expansion of
G
then
v
_G
+
e
_H
=
v
_H
+
e
_G
(where
v
_G
,
e
_H
,
v
_H
, and
e
_G
denote respectively the number of vertices of
G
, the number of edges of
H
, the number of vertices of
H
, and the number of edges of
G
).

10.
  
Prove: if
H
and
J
are expansions of
G
then
v
_H
+
e
_j
=
v
_J
+
e
_H
(where as above the subscripts tell us the graph whose vertices or edges are being counted).