Introduction to graph theory/Proof of Theorem 4
For a graph , the following are equivalent:
- is a tree
- is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
- is a maximal acyclic graph, in the sense that the addition of any missing edge will create a cycle.
Corollary 3: A graph is a tree if and only if for every pair of distinct vertices , there is exactly one -path.
Suppose is a tree, and let be an edge not in . By Corollary 3, there is exactly one -path. If this path is , then adding the edge will create the cycle . As a tree is defined to be a connected forest and a forest is defined to be acyclic. A tree is therefore a maximal acyclic graph.
Now suppose is a tree, and let be an edge of . By Corollary 3, there is exactly one -path. This path is clearly just the edge . Thus, in the graph , there is no -path, and hence is disconnected. Since a tree is defined to be a connected forest, a tree is therefore a minimal connected graph.
Now suppose is a maximal acyclic graph, but is not a tree. Since an acyclic graph is called a forest, and a tree is defined to be a connected forest, must be disconnected. Thus there exists vertices such that there is no -path in . In particular is not an edge of . As is a maximal acyclic graph, must have a cycle. Since has no cycle, this cycle must include the edge . Let this cycle be . Then is a -path in . This contradiction shows that maximal acyclic graphs are trees.
Finally, suppose is a minimal connected graph, but is not a tree. As a tree is defined to be a connected forest, it follows that is not a forest, and hence (by definition), must have a cycle. Let be adjacent vertices on the cycle, and let the cycle be . As is a minimal connected graph, must be disconnected. Consider any vertex . In , there was a path from to . If the path went through the edge , then in , there is clearly an -path. Otherwise, there is clearly an -path in . Either way, the connected component of contains either or . Since is a -path in , the connected component containing also contains . Thus every vertex in is contained in the same connected component, meaning that is connected. This contradiction shows that minimal connected graphs are trees.