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.