Introduction to Graph Theory (6 page)
Read Introduction to Graph Theory Online
Authors: Richard J. Trudeau
Figure 10
Figure 11
Common graphs
Some graphs have acquired more or less standard names because they turn up so frequently.
Definition 9
. If
v
is an integer greater than or equal to 3, the cyclic graph on
v
vertices, denoted “
C
v
”, is the graph having vertex set {1, 2, 3,
v
} and edge set {{1, 2}, {2, 3}, {3, 4}, ..., {(
v
â 1),
v
}, {
v
, 1}}.
Don't let the notation throw you. What we have defined is a family of infinitely many graphs called “cyclic graphs”. There is one cyclic graph for each integer, beginning with 3. To find out what a particular
member of the family looks like, say
C
5
, you simply replace all occurrences of “
v
” by 5 in the definition.
Example
.
C
5
has vertex set {1, 2, 3, 4, 5} and edge set {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}}. You can draw
C
5
yourself.
Three more cyclic graphs have been drawn in
Figure 12
.
Figure 12
Definition 10.
If
v
is a positive integer, the null graph on
v
vertices, denoted “
N
v
”, is the graph having vertex set {1, 2, 3, ...,
v
} and no edges.
There are infinitely many null graphs, one for each positive integer. The first three have been drawn in
Figure 13
. Notice that the graph
H
of two sections ago has now been given a new name,
N
5
. All graphs have at least one vertex since
Definition 5
requires that a vertex set be nonempty. Thus
N
1
is the smallest possible graph, and the only one (essentially) for which
v
= 1.
The next family of graphs is in a sense “opposite” to the null graphs.
Definition 11.
If
v
is a positive integer, the complete graph on
v
vertices, denoted “
K
v
”, is the graph having vertex set {1, 2, 3, ...,
v
} and all possible edges.
Example.
Figure 14
shows three complete graphs. Note that the graph
Figure 13
J
of two sections ago has just been renamed
K
5
.
K
1
and
N
1
are equal, as are
K
3
and
C
3
.
Figure 14
Definition 12
. The utility graph, denoted “
UG
”, is the graph having vertex set {
A
,
B
,
C
,
X
,
Y
,
Z
} and edge set {{
A
,
X
}, {
A
,
Y
}, {
A
,
Z
}, {
B
,
X
}, {
B
,
Y
}, {
B
,
Z
} {
C
,
X
}, {
C
,
Y
}, {
C
,
Z
}}.
Unlike the terms “cyclic graph”, “null graph”, and “complete graph”, that refer to infinite families of graphs, there is only one “utility graph”, drawn in
Figure 15
. The utility graph gets its name from a puzzle in which three houses (
A
,
B
, and
C
) and three utility companies (
X
,
Y
, and
Z
) are represented by dots on a sheet of paper, the task being to connect each house to each utility without crossing any lines. It cannot be done, as we shall see.
Discovery
Figure 16
is a picture of
K
16
. As you can see, the number of edges of a complete graph goes up pretty fast. Given a relatively complicated complete graph, say
K
1000
, it would be helpful if we could determine
Figure 15
Figure 16
how many edges it has without having to draw it and count them one by one. In this sectino I will develop a simple formula that does this, and I offer it as an example of how theorems are discovered in the theory of graphs.
On a piece of paper I draw the first few complete graphs. Next I count their edges and list the totals:
v | e |
1 | 0 |
2 | 1 |
3 | 3 |
4 | 6 |
5 | 10 |
6 | 15 |
7 | 21 |
8 | ? |
Now I look for a pattern to the numbers in the
e
column.
I notice one. The e's go up by consecutive integers. From 0 to 1 the jump is 1, from 1 to 3 it is 2, from 3 to 6 it is 3, from 6 to 10 it is 4, etc.
Now I notice that these jumps are the numbers in the first column, so the pattern I've found amounts to this: each
e
is the sum of the two numbers in the row above it. The 1 in the
e
column is 1 + 0, the sum of the row above; similarly the 3 is 2 + 1, the 6 is 3 + 3, the 10 is 4 + 6, etc.
I make a conjecture that my pattern is genuine, that is, that it will continue no matter how far the table is extended. I express my conjecture as an equation.
Conjecture.
For any
v
,
(no. edges of
K
v
+ 1
) = (no. vertices of
K
v
) + (no. edges of
K
v
).
Of course, the number of vertices of
K
v
is
v
, so I can rewrite my conjecture as follows:
Conjecture.
For any
v
,
(no. edges
K
v
+ 1
) =
v
+ (no. edges
K
v
).
To test this I'll try it on
K
8
, which would have been the next row of the table.
According to my conjecture, (no. edges
K
8
) = 7 + (no. edges
K
7
) = 7 + 21 = 28.
Now I draw
K
8
and count edges.
K
8
does have 28 edges. I feel pretty confident that my conjecture is right.
But while the conjecture looks good, it's really not what I want. For example, all it tells me about
K
1000
is that (no. edges
K
1000
) = 999 + (no. edges
K
999
), and I don't know the number of edges of
K
999
. Of course (no. edges
K
999
) = 998 + (no. edges
K
998
), but I don't know the number of edges of
K
998
either. I can keep going right down to the beginning, but that doesn't seem any easier than drawing K
1000
and counting directly. What I need is a pattern that doesn't involve any previous
e
's.
So I look for such a pattern. After some searching, I find one.
Each
e
is half the product of its
v
and the previous
v
. For example 1 = (1/2)(2 · l), 3 = (1/2)(3 · 2), 6 = (1/2)(4 · 3), 10 = (1/2)(5 · 4), etc. This gives me a new conjecture.
Second conjecture
. For any v
,
