Introduction to Graph Theory (20 page)

11
.
  
Find all integers
v
for which
(the complement of
C
_v
) is nonplanar. Prove that your answer is correct.

12.
  
Here is an explicit statement of the “pigeonhole principle” mentioned in the text on pages 69 and 71:

If
m
objects are distributed into
n
boxes and
m
is larger than
n
, then at least one box contains at least
m
/
n
of the objects.

Use this principle to prove that there are at least two red maples in the United States having the same number of leaves.

13.
  
Prove the following statements:

a)
  
Except for
UG
itself, no expansion of
UG
is also a supergraph of
UG
.

b)
  
Except for
K
₅
itself, no expansion of
K
₅
is also a supergraph of
K
₅
.

14.
  
Let
S
be the set of all expansions of supergraphs of
UG
or
K
₅
, and let
T
be the set of all supergraphs of expansions of
UG
or
K
₅
. We mentioned on pages 82–83 that every expansion of a supergraph of
UG
or
K
₅
is also a supergraph of an expansion of
UG
or
K
₅
, so
S
is a subset of
T
. Prove that on the other hand
T
is
not
a subset of
S
, and therefore
S
≠
T
, by finding a supergraph of an expansion of
K
₅
that is not also an expansion of a supergraph of
K
₅
.

15.
  
Isomorphism is “transitive”, that is, if
and
, then
. This enables us to prove the following theorem.

Theorem
.
If
H
is planar and
,
then
G
is planar also
.

Proof. H
is planar, so
H
is isomorphic to a graph
J
which has been drawn in a plane without edge-crossings (
Definition 18
). Since
and
,
; that is,
G
is isomorphic to a graph which has been drawn in a plane without edge-crossings. Therefore
G
is planar.

Thus planarity is yet another property preserved by isomorphism (the seventh we've mentioned). Use this fact to devise new proofs that the pairs of graphs in
Figures 46
,
51
,
54
, and
55
are not isomorphic.

16.
  
Prove that the graphs in
Figure 89
are planar.

17.
  
Prove that the graphs in
Figure 90
are nonplanar.

18–20
.
  
In
Figures 91–93
, decide whether each graph is planar or nonplanar and then prove that your choice is correct.

Figure 89

Figure 90

Figure 91