Tree Graphs

# Tree Graphs

 Definition: A graph \$G = (V(G), E(G))\$ is a Tree if it is a connected bipartite graph that contains no cycles.

Here is an example of a tree graph. Notice that this graph is both bipartite and contains no cycles: We should note that number of edges in a tree graph is always equal to one less than the number of vertices in the graph. That is, \$\mid E(G) \mid = \mid V(G) \mid - 1\$. Furthermore, since tree graphs are connected and they're acyclic, then there must exist a unique path from one vertex to another. If there exists two paths between two vertices, then there must also be a cycle in the graph and hence it is not a tree by definition.

Now suppose that \$G = (V(G), E(G))\$ is a graph on \$n\$ vertices. The following six statements in the theorem below are equivalent, that is, if one of these statements are true then the rest of these statements are true.

 Theorem 1: Let \$G = (V(G), E(G))\$ be a graph on \$n\$ vertices. Then the following statements are equivalent: a) \$G\$ is connected and acyclic. b) \$G\$ is acyclic and \$\mid E(G) \mid = n - 1\$. c) \$\mid E(G) \mid = n - 1\$ and \$G\$ is connected. d) \$G\$ is connected and the removal of any edge disconnects \$G\$. e) Any two vertices of \$G\$ are connected by only one path. f) \$G\$ contains no cycles and any addition of a new edge results in the formation of a cycle.