Introduction to Graph Theory (25 page)

Rephrased, this is “if
A
is a set containing
one horse, then all the horses in
A
are of the same color.” Obviously this is true. Next we have to prove

That is, we are given the truth of “if
A
is a set of
k
horses, then all the horses in
A
are of the same color,” and we have to deduce from this the truth of “if
A
is a set of
k
+ 1 horses, then all the horses in
A
are of the same color.” So let
A
be a set of
k
+ 1 horses. For the sake of reference we shall number the horses from 1 to
k
+ 1.

Remove horse #1. There remains a set of
k
horses. We are given that all the horses in any set of
k
horses are of the same color, so horse #2, horse #3, ..., and horse #(k + 1) must be all of the same color. Now replace horse #1 and remove horse #(
k
+ 1). Again we are left with a set of
k
horses, so horse #1, horse #2, ..., and horse #
k
must be all of the same color. Obviously then all the horses in
A
, from #1 to #(
k
+ 1), must be of the same color.

Invoking the principle of mathematical induction it follows that
S
is true for every positive integer and the theorem is proved.

Corollary.
All the horses in the world are of the same color.

Proof
. Let
A
be the set of all the world's horses, and apply the theorem to
A
.

This corollary can be used to prove a wide range of things, for example

Theorem
.
1 + 1 = 3.

Proof.
If 1 + 1 = 3, fine. If not, that would be a horse of a different color, which doesn't exist by the corollary.

  
3.
  
Believe it or not, the graph of
Figure 104a
is planar. Find
its number of faces. (If you use Euler's Formula you won't need to draw it without edge-crossings.)

Figure 104

  
4.
  
Imitate the proof of
Corollary 12
to construct a proof, independent of the results of
Chapter 3
, that the graph of
Figure 104b
is nonplanar
.

  
5
.
Crucial to the proof of Euler's Formula, the following step involves more than is immediately apparent:

Now let
G
be an arbitrary polygonal graph having
k
+ 1 faces. Remove some of the edges and vertices bordering the infinite face of
G
to produce a new polygonal graph
H
having one less face than
G
, so
H
has
k
faces.

—page 103

Find a polygonal graph
G
having a face bordering the infinite face which, if removed, results in a subgraph
H
which is not polygonal. This shows that we must be choosy about the exterior face of
G
that is removed.

  
6.
  
Prove this partial converse of Euler's Formula: if a graph is planar and
v
+
f
−
e
= 2, then the graph is connected
.

  
7
.
Definition
. A
component
of a graph is a connected subgraph that is not contained in a larger connected subgraph
.

Thus a connected graph is its own single component, and the components of a disconnected graph are what we have been calling the “pieces” that comprise it.

Examples
.
Figure 105a
has three components, which are displayed separately in 105b, c), and d).
Figure 106
has only one component, itself.

Let “
p
” denote the number of components of a graph, and prove this generalization of Euler's Formula: if a graph is planar, then
v
+
f
−
e
= 1 +
p
.

Figure 105

Figure 106

  
8.
  
Corollary 13
can sometimes be used to prove a graph
nonplanar. Use it on the graph of
Figure 106
.

  
9
.
  
Show by example that the statement “every planar graph has a vertex with degree less than or equal to 4” is false. That is, find a planar graph in which every vertex has degree greater than or equal to 5. This shows that, in this fashion at least,
Corollary 13
can't be improved upon, that it is already the strongest statement that can possibly be made
.

10.
  
There is another manner, however, in which
Corollary 13
can
be improved upon. Prove: Every planar graph with
v
≥ 4 has at least
four
vertices of degree ≤ 5
.

11.
Definition.
The
connectivity
of a graph is the smallest number of vertices whose removal (together with their incident edges) results in either
K
₁
or a disconnected graph. We shall denote the connectivity of a graph by “
c
”
.

Examples
. Removing vertices with their incident edges never disconnects
K
₄
, but after removing three vertices (with edges) we are left with
K
₁
, so
K
₄
has
c
= 3. The graph of
Figure 105a
has
c
= 0 as it is already disconnected.
Figure 105b
has
c
= 2,
105c
has
c
= 1,
105d
has
c
= 2, and
106
has
c
= 6.

The connectivity of a graph indicates the
extent
to which it is connected, in some sense. Note that
c
is a
minimum.
If you were to remove successively vertices 3, 1, 6, and 4 from
Figure 79b
you might erroneously conclude that the graph has
c
= 4, as the debris was disconnected only after the fourth removal. But starting over and removing vertices 2 and 9 shows that
c
can be at most 2.
c
is exactly 2 since the removal of any one vertex leaves a connected subgraph. Find
c
for each of the graphs in
Figures 91
,
92
, and
93
.

12
.
  
By
Exercise 11
of Chapter 2, 2
e
/
v
is the average of the degrees of a graph. Prove that if a graph has connectivity
c
then
c
is less than or equal to 2
e
/
v
.

13.
  
Use the previous exercise to show that there is no graph with
e
= 7 and
c
= 3, and none with
e
= 11 and
c
= 4
.

14.
Definition
. A
bridge
in a graph is an edge whose removal would increase the number of components
.

Example
.
In
Figure 107
there are six bridges: {1, 2}, {12, 13}, {4, 5}, {6, 7}, {7, 8}, and {18, 19}. The graph has two components; if any bridge were removed the resulting subgraph would have three components.

Figure 107

In a planar graph a bridge necessarily borders on only one face,
and an edge bordering on only one face is necessarily a bridge. Thus bridges are the things that prevent planar connected graphs from being polygonal. Use this fact to prove that if a planar and connected graph
G
has the property that the boundary of every face is a cyclic graph, then
G
is polygonal. Then show that the converse statement is false by finding a polygonal graph having a face whose boundary is not a cyclic graph.

15
.
  
By
Theorem 11
we know that every planar, connected graph with
v
≥ 3 has
e
≤ 3
v
− 6. Prove that if such a graph
G
has the additional property that every supergraph of
G
with one more edge is nonplanar, then the boundary of every face of
G
is
C
₃
,
G
is polygonal, and
G
has
e
= 3
v
− 6
.