Introduction to graph theory/Proof of Theorem 4
From Wikiversity
Contents |
[edit] Statement
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] Corollary of
Corollary 3: A graph is a tree if and only if for every pair of distinct vertices u,v, there is exactly one u,v-path.
[edit] Proof
Suppose G is a tree, and let uv be an edge not in G. By Corollary 3, there is exactly one u,v-path. If this path is 
, then adding the edge uv 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 G is a tree, and let uv be an edge of G. By Corollary 3, there is exactly one u,v-path. This path is clearly just the edge uv. Thus, in the graph G − uv, there is no u,v-path, and hence G − uv is disconnected. Since a tree is defined to be a connected forest, a tree is therefore a minimal connected graph.
Now suppose G 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, G must be disconnected. Thus there exists vertices u,v such that there is no u,v-path in G. In particular uv is not an edge of G. As G is a maximal acyclic graph, G + uv must have a cycle. Since G has no cycle, this cycle must include the edge uv. Let this cycle be . Then is a u,v-path in G. This contradiction shows that maximal acyclic graphs are trees.
Finally, suppose G is a minimal connected graph, but is not a tree. As a tree is defined to be a connected forest, it follows that G is not a forest, and hence (by definition), G must have a cycle. Let u,v be adjacent vertices on the cycle, and let the cycle be . As G is a minimal connected graph, G − uv must be disconnected. Consider any vertex x. In G, there was a path from x to v. If the path went through the edge uv, then in G − uv, there is clearly an x,u-path. Otherwise, there is clearly an x,v-path in G − uv. Either way, the connected component of G − uv contains either u or v. Since is a u,v-path in G − uv, the connected component containing u also contains v. Thus every vertex in G − uv is contained in the same connected component, meaning that G − uv is connected. This contradiction shows that minimal connected graphs are trees.
