Introduction to graph theory/Proof of Theorem 5
From Wikiversity
Contents |
[edit] Statement
A tree of order n has n − 1 edges.
[edit] Corollary of
Theorem 4:For a graph G, the following are equivalent:
- G is a tree
- G is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
- G is a maximal acyclic graph, in the sense that the addition of any missing edge will create a cycle.
[edit] Proof
For n = 1, all graphs have 0 = n − 1 edges. For n = 2, there are two graphs, one with an edge and one without. The graph without an edge is disconnected, and therefore is not a tree, whereas the one with an edge is connected and has no cycles and therefore is a tree.
For n = 3, there are 4 graphs, one each with 0, 1, 2 or 3 edges. The graphs with 0 and 1 edges are disconnected, while the graph with 3 edges has a cycle. The graph with 2 edges is connected and has no cycle, so the theorem is proved for 
.
Now suppose we have proved this theorem for all n < k, and let T be a tree of order k. Remove an edge e from T to form a new graph T − e. By Theorem 4, T is a minimal connected graph, and hence T − e is disconnected. Any connected component of T − e (by the connectedness of T) must have one of the vertices of e in it, and hence T − e has exactly two components.
The two components are connected, and have no cycles, and are therefore trees. Let there be n1,n2 vertices in the two components of T − e. Then n1 + n2 = k. Further, there are n1 − 1,n2 − 1 edges in the components, so T − e has k − 2 edges in total. Therefore, putting edge e back into the graph, T has k − 1 edges.
