# Introduction to graph theory/Proof of Theorem 4

## Statement

For a graph ${\displaystyle G}$, the following are equivalent:

• ${\displaystyle G}$ is a tree
• ${\displaystyle G}$ is a minimal connected graph, in the sense that the removal of any edge will leave a disconnected graph.
• ${\displaystyle 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 ${\displaystyle u,v}$, there is exactly one ${\displaystyle u,v}$-path.

## Proof

Suppose ${\displaystyle G}$ is a tree, and let ${\displaystyle uv}$ be an edge not in ${\displaystyle G}$. By Corollary 3, there is exactly one ${\displaystyle u,v}$-path. If this path is ${\displaystyle ux_{1}\ldots x_{k}v}$, then adding the edge ${\displaystyle uv}$ will create the cycle ${\displaystyle 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 ${\displaystyle G}$ is a tree, and let ${\displaystyle uv}$ be an edge of ${\displaystyle G}$. By Corollary 3, there is exactly one ${\displaystyle u,v}$-path. This path is clearly just the edge ${\displaystyle uv}$. Thus, in the graph ${\displaystyle G-uv}$, there is no ${\displaystyle u,v}$-path, and hence ${\displaystyle G-uv}$ is disconnected. Since a tree is defined to be a connected forest, a tree is therefore a minimal connected graph.

Now suppose ${\displaystyle 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, ${\displaystyle G}$ must be disconnected. Thus there exists vertices ${\displaystyle u,v}$ such that there is no ${\displaystyle u,v}$-path in ${\displaystyle G}$. In particular ${\displaystyle uv}$ is not an edge of ${\displaystyle G}$. As ${\displaystyle G}$ is a maximal acyclic graph, ${\displaystyle G+uv}$ must have a cycle. Since ${\displaystyle G}$ has no cycle, this cycle must include the edge ${\displaystyle uv}$. Let this cycle be ${\displaystyle ux_{1}\ldots x_{k}vu}$. Then ${\displaystyle ux_{1}\ldots x_{k}v}$ is a ${\displaystyle u,v}$-path in ${\displaystyle G}$. This contradiction shows that maximal acyclic graphs are trees.

Finally, suppose ${\displaystyle G}$ is a minimal connected graph, but is not a tree. As a tree is defined to be a connected forest, it follows that ${\displaystyle G}$ is not a forest, and hence (by definition), ${\displaystyle G}$ must have a cycle. Let ${\displaystyle u,v}$ be adjacent vertices on the cycle, and let the cycle be ${\displaystyle ux_{1}\ldots x_{k}vu}$. As ${\displaystyle G}$ is a minimal connected graph, ${\displaystyle G-uv}$ must be disconnected. Consider any vertex ${\displaystyle x}$. In ${\displaystyle G}$, there was a path from ${\displaystyle x}$ to ${\displaystyle v}$. If the path went through the edge ${\displaystyle uv}$, then in ${\displaystyle G-uv}$, there is clearly an ${\displaystyle x,u}$-path. Otherwise, there is clearly an ${\displaystyle x,v}$-path in ${\displaystyle G-uv}$. Either way, the connected component of ${\displaystyle G-uv}$ contains either ${\displaystyle u}$ or ${\displaystyle v}$. Since ${\displaystyle ux_{1}\ldots x_{k}v}$ is a ${\displaystyle u,v}$-path in ${\displaystyle G-uv}$, the connected component containing ${\displaystyle u}$ also contains ${\displaystyle v}$. Thus every vertex in ${\displaystyle G-uv}$ is contained in the same connected component, meaning that ${\displaystyle G-uv}$ is connected. This contradiction shows that minimal connected graphs are trees.