Introduction to Graph Theory (7 page)

I check if this squares with the first conjecture. The first conjecture said that (no. edges
K
<sub>v
+ 1</sub>
) =
v
+ (no. edges
K
_v
). By the second conjecture (no. edges
K
<sub>v
+ 1</sub>
) = (1/2)(
v
+ 1)(
v
) and (no. edges
K
_v
) = (1/2)(
v
) · (
v
− 1); substituting these values into the first conjecture I get

The last equation is true, so I conclude that my two conjectures are compatible. They are both true or both false. I don't know for a fact that either one is true, but if I'm wrong I have to be doubly wrong.

Furthermore, I notice that the second conjecture, if true, is exactly the sort of thing I want. With it there's no problem to finding the number of edges of
K
₁₀₀₀
: no. edges
K
₁₀₀₀
= (1/2)(1000)(999) = (1/2) · (999, 000) = 499, 500. So the second conjecture really seems to be it.

Of course now I have to prove it, if I can.

I try to think of a reason why the second conjecture would have to be true for any complete graph.

I get it by noticing that the number of edges in a graph is half the number of edge-ends. Let me write this up for you formally. My second conjecture is now a theorem.

Theorem 2
. The number of edges in a complete graph
K
_v
is given by the formula
e
= (1/2)
v
(
v
− 1).

Proof. We will count the number of edge-ends in
K
_v
.
K
_v
has
v
vertices. Each vertex is joined to the other
v
− 1 vertices, so at each vertex there are
v
− 1 edge-ends. Therefore the total number of edge-ends in
K
_v
is
v
(
v
− 1). Every edge has two ends, so the number of edges in
K
_v
is half the number of edge-ends, or (1/2)
v
(
v
− 1).

Complements and subgraphs

Heretofore the letters “
G
”, “
H
”, and “
J
” have been used only in reference to three specific graphs introduced a few sections ago. But from now on we will use them as convenient names for whatever graphs are under discussion, much as an algebraist would use “
x
”, “
y
”, and “
z
” to denote whatever unknown quantities he or she was considering at the moment.

Definition 13
. If
G
is a graph then the complement of
G
, denoted “
G
”, is a graph having the same vertex set; the edge set of
G
consists of all two-element subsets of the vertex set which have not already been included in the edge set of
G
.

Thus
G
has the same vertices as
G
but the edges are in the “opposite” places. If two vertices are connected in G, they are not connected in
G
; and if two vertices are not connected in
G
, then they are connected in
G
.

Examples
.
1) The complements of the first three cyclic graphs are shown in
Figure 17a, b
), and
c
).

2) Null graphs and complete graphs are complementary. That is, for every positive integer
v
,
N
_v
is equal to
K
_v
and
K
_v
is equal to
N
_v
.

3)
Figure 17d, e
), and
f
) are all
UG
.

Figure 17

Note that for any graph
G
, the complement
G
is also a graph, so we may take its complement
G
; and that when this is done the result is the original graph
G
.

Definition 14
. A graph
H
is a subgraph of a graph
G
if the vertex set of
H
is a subset of the vertex set of
G
and the edge set of
H
is a subset of the edge set of
G
.

Examples
.
1) In
Figure 18
the first five graphs are all subgraphs of the sixth.

2)
C
₄
is a subgraph of
K
₅
. For that matter, so are
C
₃
,
C
₅
,
N
₁
N
₂
,
N
₃
,
N
₄
,
N
₅
,
K
₂
,
K
₄
, and
K
₅
. And there are scores of others that we haven't given names to.

3)
C
₄
is a subgraph of
K
₄
, which in turn is a subgraph of
K
₆
.

A subgraph is a graph contained in another graph. Note that since every set is a subset of itself, every graph is a subgraph of itself. Intuitively a subgraph is the result of attacking a graph with an eraser, with two qualifications: you needn't erase anything, since every graph is a subgraph of itself; and though you may erase edges as much as you want, you must not erase a vertex without also erasing all edges incident to it, or the result will not be a graph (see item 2 in the “Cautions” section).

Figure 18

Isomorphism

Something peculiar is going on in
Figure 19
. The first two graphs are equal, the last two graphs are equal, but the middle two aren't. That hardly seems right, because the only difference between b) and c) lies in how the vertices have been labeled. As we have defined the term “equal”, however (see
Definition 8
), there's no doubt that b) and c) are not equal, for their vertex sets {
P
,
Q
,
R
,
S
,
T
,
U
} and {1, 2, 3, 4, 5, 6} are unequal sets and their edge sets are unequal also.

We obviously need a new concept, one that will make our mathematics sensitive to the kind of “sameness” we intuitively attribute to graphs b) and c). Such a concept exists; it is called “isomorphism”, from Greek roots meaning “same structure”. The notion of isomorphism is fundamental to the theory of graphs, so I plan to discuss it at some length, beginning with a precise definition. But first a preliminary definition.

Figure 19

Definition 15
. If
A
and
B
are sets, then a
one-to-one correspondence
between
A
and
B
is an association of elements of
A
with elements of
B
in such a way that

      
(1)
  
to each element of
A
there has been associated a single element of
B
, and

      
(2)
  
to each element of
B
there has been associated a single element of
A
.

Thus the presence of a one-to-one correspondence between two finite sets means that they at least have the same number of elements. But there is something more. Each element of each set has been made to correspond with a particular element of the other set. So if
q
is an element of
A
, one may speak of “the element of
B
corresponding to
q
.” A simple way of displaying a one-to-one correspondence is to draw arrows between corresponding elements.

Examples.
If
A
= {1, 2, 3, 4, 5, 6, 7, 8} and
B
= {&, +, !, ?, %,
#
, ÷, $}, then

is a one-to-one correspondence between
A
and
B
, and