Theorem 1 (Handshake lemma)
Let be a simple nondirected finite graph. Then
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.
A simple finite undirected graph has 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 maximum degree of a node in a finite tree cannot exceed the number of leaves of the tree, because each subtree of any node contains at least one leaf.
A finite tree with exactly three leaves is homeomorphic to .
Proof. A finite 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.
A finite 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.
|Date of creation||2013-03-22 18:01:52|
|Last modified on||2013-03-22 18:01:52|
|Last modified by||Ziosilvio (18733)|