Introduction to Graph Theory (12 page)

These numbers are computed using something called the “Polya Enumeration Theorem”, which is too difficult to take up in this book.

Figure 45

There is no simple way of determining the number of graphs having a given
v
.

Exercises

  
1.
  
List all subsets of the set {1, 2, 3}. There are eight of them.

  
2.
  
It follows from the Law of Excluded Middle (page 18) that to prove a mathematical statement true, it suffices to show that it cannot be false. Letting
A
be a set and
j
an empty set, show that the statement “
J
is a subset of
A
” cannot be false and so is true. This proves that an empty set is a subset of every set and promotes the Convention on page 14 to Theorem.

  
3.
  
This is another version of Russell's Paradox. The village barber shaves those and only those men who live in the village and do not shave themselves. The village barber is a man and he lives in the village.

Consider the question “Who shaves the barber?” Then explain how this situation is equivalent to Russell's Paradox.

  
4
.
  
Let “
S
” be the collection of all sets that can be described in an English sentence of twenty-five words or less. Is
S
a set? Why or why not?

  
5.
  
If
v
is an integer greater than or equal to 2, the path graph on
v
vertices, denoted “
P
_v
”, is the graph having vertex set {1, 2, 3, . . .,
v
} and edge set

Draw the first five path graphs. Then find and prove a formula analogous to
Theorem 2
for the number of edges of
P
_v
.

  
6.
  
If
v
is an integer greater than or equal to 4, the wheel graph on
v
vertices, denoted “
W
_v
”, is the graph having vertex set {1, 2, 3, ...,
v
} and edge set {{1, 2}, {1, 3}, ..., {1,
v
}, {2, 3}, {3, 4}, ..., {
v
− 1,
v
}, {
v
, 2}}. Draw the first five wheel graphs. Then find and prove a formula analogous to
Theorem 2
for the number of edges of
W
_v
.

  
7
.
  
Use
Theorem 2
to prove that

for any integer
v
greater than or equal to 2. Do not use any arithmetic or algebra.

  
8
.
  
Let
G
be a graph with
v
vertices and
e
edges. In terms of
v
and
e
, how many edges has
G
?

  
9
.
  
Prove: if a graph
G
has
v
= 6 then
G
or
G
(possibly both) has a subgraph isomorphic to
K
₃
.

10.
  
Use
Exercise 9
to prove that in any gathering of six people there are either three people who are mutually acquainted or three people who are mutually unacquainted, possibly both.

11.
  
Prove: the sum of the degrees of the vertices of a graph is 2
e
.

12.
  
Use
Exercise 11
to answer these questions:

        
a)
  
If a graph has
v
= 9, 4 vertices of degree 3, 2 vertices of degree 5, 2 of degree 6 and 1 of degree 8, how many edges has the graph?

        
b)
  
UG has
v
= 6 and every vertex has degree 3; prove that there are however no graphs with
v
= 7 in which every vertex has degree 3.

13
.
  
Prove that
C
₅
≅
C
₅
. Then prove that no other cyclic graph is isomorphic to its complement.

14.
  
Prove: If
G
≅
G
then
v
or
v
− 1 is a multiple of 4. (You might use
Theorem 2
and the fact that isomorphic graphs have the same number of edges.)

15.
  
If
G
≅
G
,
G
is called a “self-complementary” graph.
Exercise 13
says that
C
₅
is self-complementary and is the only cyclic graph that is. Find two other self-complementary graphs. (You might use
Exercise 14
to narrow your search.)

16
.
  
Find a self-complementary graph with
v
= 8. Of the 12, 346 graphs with
v
= 8 only four are self-complementary.

17.
  
Since there are an odd number of graphs having
v
= 4 (drawn in
Figure 45
), one of them must be self-complementary. Which one?

18.
  
How many different one-to-one correspondences are there between {
a
,
b
,
c
,
d
,
e
,
f
,
g
,
h
,
i
,
j
} and {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}? (Two one-to-one correspondences are “different” if there is at least one element that they associate with different elements.)

19.
  
We said in the text that the existence of a one-to-one correspondence between two finite sets implies that they contain the same number of elements. The situation for infinite sets is somewhat different. The set of positive integers {1, 2, 3, ...} in some sense contains “twice as many” elements as the set of even positive integers {2, 4, 6, ...}, yet it is possible to put the two sets into a one-to-one correspondence. Do so.

20
.
  
Besides the four properties mentioned in the text, another property preserved by isomorphism is the distribution of subgraphs. That
is, if two graphs are isomorphic and you select a subgraph at random from either one, then the other will necessarily have an isomorphic subgraph. Hence you can prove that two graphs are not isomorphic by finding a subgraph of one that is not a subgraph of the other. Use this fact to devise a proof, shorter than the one in the text, that the graphs of
Figure 35
are not isomorphic.

Figure 46

Figure 47

Figure 48

21.
  
K
₃
(with its vertices labeled) has 17 unequal subgraphs. Draw them.

22.
  
The number of
nonisomorphic
subgraphs of
K
₃
is only 7. Draw them.

23.
  
The graphs of
Figure 46
are not isomorphic. Prove this by finding a subgraph of one that is not a subgraph of the other.

24.
  
Satisfy yourself that isomorphic graphs have isomorphic complements and that consequently nonisomorphic graphs have nonisomorphic complements. Then use this fact to devise a proof, different from the one in the text, that the graphs of
Figure 31
are not isomorphic.