Introduction to graph theory/Proof of Theorem 4

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.

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.

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 $ux_1\ldots x_kv$, then adding the edge $uv$ will create the cycle $ux_1\ldots x_kvu$. 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 $ux_1\ldots x_kvu$. Then $ux_1\ldots x_kv$ 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 $ux_1\ldots x_kvu$. 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 $ux_1\ldots x_kv$ 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.