Read Introduction to Graph Theory for Free Online

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
,

    I check if this squares with the first conjecture. The first conjecture said that (no. edges
K
v
+ 1 ) =
v
+ (no. edges
K
v ). By the second conjecture (no. edges
K
v
+ 1 ) = (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
1000 : no. edges
K
1000 = (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