3.5c Trees

Tree (Connected and Acyclic Graph)

A tree is a bipartite graph that is both connected and acyclic (contains no cycles) (i.e., when one node is disconnected, the graph becomes disconnected). A graph that is not connected and acyclic is called a forest, and consist of more than one tree. Trees consist of a root, internal nodes, and leaf nodes. The following are all equivalent definitions of a tree $G=(V,E)$:

1. $G$ is connected and contains no cycles.
2. $G$ is connected and has exactly $|V|-1$ edges.
3. $G$ is connected and the removal of any edge disconnects $G$.
4. $G$ is acyclic and the addition of any edge creates a cycle in $G$.

Properties

$G$ has exactly $|V|-1$ edges.

Backward direction. Proceed by contradiction.

• If $G$ is connected and has $n-1$ edges, then it is acyclic.
• However, if $G$ had $n-1$ edges and contained a cycle, then removing one of the cycle’s edges does not disconnect the graph. Therefore, we can create a tree with $n-2$ edges. However, a graph that contains less than $n-1$ edges is always disconnected (see 3.1).

All trees are bipartite.

For all trees, $f=1$.

Since trees are acyclic by definition, it only follows that the plane will not be subdivided into extra faces.