|
We recall that the degree (sometimes called valency) of a vertex  of an undirected graph  is the number  of  's neighbors, i.e., the number of vertices 
of  such that an edge  exists.
Theorem 1 (Handshake lemma) Let  be a simple nondirected finite graph. Then
 |
(1) |
Proof. List all the edges of  , with their endpoints, each edge once. Each vertex  occurs a number of times equal to the number of edges  is an endpoint of, i.e., the number  of its neighbors. On the other hand, each edge has two endpoints, thus the sum of all occurrences of vertices must equal twice the number of edges.
Corollary 1 In a simple finite undirected graph, there is an even number of vertices of odd degree.
Proof. By the handshake lemma, the sum of the degrees of all vertices of odd degree must be even, which is only possible if their number is even.
The following two statements about trees also follow from the handshake lemma. Recall that the number of leaves in a tree cannot exceed the maximum degree of a node in the tree, because each subtree of any node contains at least one leaf.
Corollary 2 Any tree with exactly three leaves is homeomorphic to  .
Proof. A tree with three leaves can have no vertex of degree greater than 3. By the handshake lemma, the number of vertices of odd degree must be even: this forces a vertex of degree 3 to exist. Such a vertex is also unique, because if there were two, the tree would have at least four leaves. All the other vertices, except the leaves, have degree 2, and it is possible to contract them all to get  ; such a sequence of contractions is in fact a graph
homeomorphism.
Corollary 3 Any tree with exactly four leaves is homeomorphic to either  or two joint copies of  .
Proof. If a vertex of degree 4 exists, then no other vertex of degree greater than 2 can exist, or the tree would have five or more leaves. Otherwise, a vertex of degree 3 must exist, or the tree would be a streamline with only two leaves; by the handshake lemma, there must be another one, and no more, or the tree would have at least five leaves. All the other vertices, except the leaves, have degree 2, and it is possible to contract them all to get either  (if there is a vertex of degree 4) or two joint copies of  (if there are two vertices of degree 3); such a sequence of contractions is in fact a graph homeomorphism.
|
