Introduction to Graph Theory (6 page)

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
₅
, you simply replace all occurrences of “
v
” by 5 in the definition.

Example
.
C
₅
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
₅
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
₅
. All graphs have at least one vertex since
Definition 5
requires that a vertex set be nonempty. Thus
N
₁
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
₅
.
K
₁
and
N
₁
are equal, as are
K
₃
and
C
₃
.

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
₁₆
. As you can see, the number of edges of a complete graph goes up pretty fast. Given a relatively complicated complete graph, say
K
₁₀₀₀
, 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:

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
<sub>v
+ 1</sub>
) = (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
<sub>v
+ 1</sub>
) =
v
+ (no. edges
K
_v
).

To test this I'll try it on
K
₈
, which would have been the next row of the table.

According to my conjecture, (no. edges
K
₈
) = 7 + (no. edges
K
₇
) = 7 + 21 = 28.

Now I draw
K
₈
and count edges.

K
₈
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
₁₀₀₀
is that (no. edges
K
₁₀₀₀
) = 999 + (no. edges
K
₉₉₉
), and I don't know the number of edges of
K
₉₉₉
. Of course (no. edges
K
₉₉₉
) = 998 + (no. edges
K
₉₉₈
), but I don't know the number of edges of
K
₉₉₈
either. I can keep going right down to the beginning, but that doesn't seem any easier than drawing K
₁₀₀₀
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
,