# 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_{k}v$ , then adding the edge $uv$ will create the cycle $ux_{1}\ldots x_{k}vu$ . 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_{k}vu$ . Then $ux_{1}\ldots x_{k}v$ 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_{k}vu$ . 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_{k}v$ 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.