Introduction to Graph Theory (44 page)

16
.
  
See
Figure 161
. The names are those of students who found them.

Figure 161

20
.
  
In
Figure 35
, only the left graph contains a subgraph isomorphic to
C
₈
.

30–37
.
  
The pairs in
Figures 50
,
52
,
53
, and
56
are isomorphic; the pairs in
Figures 49
,
51
,
54
, and
55
are not.

40
.
  
See
Figure 162
.

Figure 162

Chapter 3. Planar Graphs

1(c)
.
  
In order to have (1/2)(
v
+ l) edges with no two adjacent we would need two vertices per edge or
v
+ 1 distinct vertices.

4
.
  
The self-complementary graphs in
Figure 161
are all planar.

11
.
  
C
_v
is nonplanar for
v
≥ 7.

18–20
.
  
Planar: 91(a), 93(a), 93(b). Nonplanar: 91(b), 92(a), 92(b).

Chapter 4. Euler's Formula

2
.
  
In the paragraph beginning, “Remove horse
#
1,” the argument is invalid if the set
A
contains only two horses.

5
.
  
See
Figure 163
. If the middle face is eliminated by removing either (or both) of the marked edges, the result is not polygonal.

Figure 163

7
.
  
Applying Euler's Formula to each component, we get

where the subscripts denote the components. Adding gives us

where
p
− 1 has been added to
f
because the sum
f
₁
+
f
₂
+ . . . +
f
_p
counts the infinite face
p
times instead of just once.

9
.
  
The icosahedron in
Figure 109
fills the bill.

12
.
  
Since it is impossible for every degree to be larger than the average, there is at least one vertex, “
A
,” whose degree
d
is ≤ 2
e
/
v
. Since removing the
d
vertices adjacent to
A
, together with their incident edges, will disconnect
A
from what is left of the graph—or if nothing is left, result in
K
₁
—we see that
c
≤
d
. Combining the two inequalities yields the result.

15
.
  
An edge bordering only one face would allow at least one edge to be added without causing an edge-crossing, so every edge of
G
must border two faces and
G
must be polygonal. Similarly, within a face bounded by more than three edges at least one extra edge could be added without causing a crossing, so the boundary of every face must be
C
₃
. Thus 3
f
= 2
e
or
f
= (2/3)
e
, and this can be substituted into Euler's Formula.

Chapter 5. Platonic Graphs

4
.
  
By
Lemma 14
, 10 = 6
d
/2 or 10 = 3
d
, an impossibility.

6
.
  
See
Figure 164
, or
Figure 55(b)
.

Figure 164

Chapter 6. Coloring

2
.
  
For graphs (a) and (c),
X
= 3. For graph (b),
X
= 4.

3
.
  
If a graph has
X
= 2 then, because null graphs have
X
= 1, it must have at least one edge; and because odd cyclic graphs have
X
= 3, it must have no odd cyclic subgraphs.

Conversely, suppose a graph
G
has at least one edge and no odd cyclic subgraphs. Let “
H
” be any connected component of
G
(see the Definition on p. 113) having at least one edge (if
G
is connected, then
H
=
G
). We will describe how to color
H
with two colors. Let “
A
” be any vertex in H. Let the
distance
from
A
to another vertex in
H
be the minimum number of edges in any walk from
A
to that vertex. Color
A
and the vertices at an even distance from
A
with color 1, and color the vertices at an odd distance from
A
with color 2. If any edge {
B
,
C
} of
H
were now to join two vertices of the same color, then the divergent ends of minimal walks from
A
to
B
and
A
to
C
, together with {
B
,
C
} itself, would form an odd cyclic subgraph, which is an impossibility; so
H
has been colored with two colors. Thus every component of
G
having at least one edge can be colored with two colors, meaning that
G
can too.

5
.
  
Let “
v
₁
” be the number of vertices in
G
that have received color 1. Then no pair of them are adjacent, meaning that over in
G
every pair of them are adjacent and they require
v
₁
different colors. Thus
X
≥
v
₁
. Arguing analogously for each of the other colors in
G
gives us

—from which it follows, by addition, that
X
X
≥
v
.

Chapter 7. The Genus of a Graph

6
.
  
Use
Corollary 22a
.

13
.
  
Respectively,
f
= 5,
f
= 7, and
f
= 21.

15
.
  
Since the boundary of every face is
K
₃
, 3
f
= 2
e
or
f
= (2/3)
e
; substitute this into Euler's Second Formula.

20
.
  
A square prism with a square hole (
Figure 144
), a pentagonal prism with a pentagonal hole (the Pentagon Building), a hexagonal prism with a hexagonal hole, and so on.

21
.
  
The genus is no less than 4 because whenever
g
< 4,
X
(
S
_g
) < 10 by the Heawood Coloring Theorem. The genus is no more than 6 by
Corollary 22
.

25
.
  
Apply
Exercise 15
, p. 116, to get
e
= 3
v
− 6.