Proof:   Since G is a tree, it is also a connected graph; and since it has at least two vertices, E(G) ¹ Æ must hold (see (d) in the proof of Theorem 5 above). Start a walk at some u Î V(G) along some edge e incident with u; e cannot be a loop since G is acyclic; so e joins u and v ¹ u. If d(v)=1, i.e., e is the only edge incident with v, then v is an endvertex; otherwise continue the walk along some f ¹ e. Repeating the argument, we note:

(i)   in continuing the walk we always choose the edge at a vertex of degree > 1, which is different from those edges already traversed;

(ii)   because of (i) and since G is acyclic we cannot reach a vertex passed before (think this through!).

Thus, since V(G) and E(G) are finite sets, this walk (which is a path indeed) must terminate at some vertex t from which the walk cannot be continued along an edge not yet traversed. That is, d(t)=1, hence t is an endvertex. t ¹ u, but t=v is possible (see above).

Now we look at u. If d(u)=1, then u,t are two endvertices, and nothing is left to be proved. So assume d(u) > 1, and start at u another walk traversing e¢ ¹ e first (such e¢ incident with u exists because of d(u) > 1). Observing that (i) and (ii) also hold w.r.t. this second walk, and hold in this case even w.r.t. vertices passed in the first walk, we conclude that the second walk will terminate at some w ¹ t such that d(w)=1. That is, t and w are two different endvertices of G. \blacksquare

In fact, this Lemma will be used in the following criterion which characterizes trees by a simple relationship between the respective numbers of vertices and edges.

Theorem 7   A connected graph G on p vertices and q edges is a tree if and only if q=p-1.

Proof:   Since the theorem says `if and only if', we must proceed in two steps, starting from the hypothesis that G is connected.

Step 1:  Suppose the connected graph G on p vertices and q edges is a tree. We want to show that q=p-1 (that is the `only if' part, the necessary condition).

If G has just one vertex, then E(G)=Æ follows of necessity in this case: i.e., p=1,q=0 implying q=0=1-1=p-1. So the claimed equation holds for a tree with just one vertex.

If G has more than one vertex, then G being a tree implies (by Lemma 6) that G has at least two endvertices. Let t Î V(G) be one of them, and let f be the only edge incident with t. Then

G1:=G-{t,f}

is also a tree (think this through!), and it has one vertex less than G. Since the equation has been proved for p=1, we may invoke induction: so if G₁ has p₁ vertices and q₁ edges, then q₁=p₁-1. On the other hand, p=p₁+1,q=q₁+1 by construction of G₁. Whence q=q₁+1=(p₁+1)-1=p-1 implying the validity of the equation for G as well. [As an exercise, prove this part of the proof of the theorem, by contradiction].

Step 2:  Suppose for the connected graph G that its number of vertices, p, and its number of edges, q, satisfy q=p-1. We want to show that G is a tree. In any case, by Theorem 5, G contains a spanning tree T. T has p¢=p vertices and q¢ £ q edges. Now, since T is a tree, we know from Step 1, the first part of the proof of this theorem, that q¢=p¢-1; and q=p-1 holds by assumption. Combining these two equations and using p¢=p,q¢ £ q, we obtain

q ³ q¢=p¢-1=p-1=q

from which q¢=q follows. That is T=G, so G is a tree indeed. \blacksquare

Note that if we had proved Step 1 of the proof of Theorem 7 before proving Theorem 5 (in this Step 1 and in the proof of Lemma 6, no use of Theorem 5 has been made), then we could have proved Theorem 5 by induction on the number of edges of G, instead of proceeding by induction on the number of cycles (get issue 7.2 and check this carefully!).

Trees play an important role in graph theory - but they originate from considerations in organic chemistry! And this is where we want to turn to, now.

Let us consider the alkanes: their formula is C_nH_2n+2. But what are their structure formulae? Don't worry, if you have forgotten. Let us just consider the structure formulae for n=1,2; and the corresponding abstract graphs (for this is what structure formulae of chemical compounds are!).

The graph G_n corresponding to C_nH_2n+2 has

p=n+(2n+2)=3n+2

vertices. The Handshaking Lemma (Theorem 3 in issue 6.3),
\dså_i=1^p d(v_i)=2q, applied to this special case yields

n·4+(2n+2)·1 = 2q, i.e., q=3n+1

(observe that in this case, the first n terms in the sum are all 4, while the others are all 1). That is, the graphs G_n, n=1,2,¼, with p=3n+2 and - as just shown - q=3n+1 thus satisfy q=p-1. Since we are not dealing with polymers, the molecules C_nH_2n+2 correspond to connected (!) graphs. So, G_n is a connected graph satisfying q=p-1. By Theorem 7, G_n is a tree for every n. Quite amazing indeed how much one can say about the alkanes by using very little of their chemical properties!

But that's not all! If we look at the subgraphs T_n of G_n which we obtain by deleting all the endvertices of G_n (together with the corresponding edges), then these T_n are also trees - called carbon trees. Now, T₁,T₂,T₃ are uniquely determined, but for T₄ we have two possibilities (see Figure 5). And for n > 4 the number of different carbon trees T_n grows larger and larger (determine all possibilities for T₅ and T₆). That is, through graph theoretical considerations we are led to the possible existence of isomers. Which of the possible carbon trees T_n actually appear in reality, is to be decided by chemical and physical properties of C_nH_2n+2. However, graph theory can say how many isomers of the form C_nH_2n+2 may possibly exist.