Introduction to graph theory/Proof of Theorem 4

Statement

edit

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 of

edit

Corollary 3: A graph is a tree if and only if for every pair of distinct vertices  , there is exactly one  -path.

Proof

edit

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.

Comments

edit