# Tree/Proof of properties of trees

*Theorem*: For a simple graph, any two of these three statements, taken together, imply the third:

- The graph is connected.
- The graph is acyclic.
- The number of vertices in the graph is exactly one more than the number of edges.

*Proof*: By induction. In a graph with one vertex, all three statements hold, so the claim is trivially true. Now suppose that the claim holds for all simple graphs with vertices (where ). We show it holds for all graphs with vertices:

- Suppose a simple graph has vertices and it is connected and acyclic. Choose any vertex . Clearly has degree at least one, since the graph is connected. If has degree one, stop. If not, choose any edge incident upon and denote the other endpoint . If has degree one, stop; otherwise choose a different edge out of and denote the other endpoint ; keep following this procedure until reaching a vertex of degree one. (This procedure must terminate, otherwise the vertices of the graph would be exhausted and a cycle would be formed, a contradiction.) Let be minus this vertex and its single incident edge. Clearly is still connected and acyclic and has vertices; therefore it has edges by the inductive hypothesis. Therefore has edges.
- Suppose a simple graph has vertices, is connected, and has edges. Since the graph is connected, all vertices have degree at least one. If every vertex has degree at least two, then the sum of degrees is at least , so, by the handshake lemma, there are at least vertices, a contradiction; therefore at least one vertex must have degree one. Let be the graph obtained by removing this vertex and its incident edge from . Then is still connected and it has vertices and edges; by the inductive hypothesis, it is acyclic. Adding a single vertex and connecting it
*via*a single edge to regenerate clearly does not introduce any cycles. - Suppose a simple graph is acyclic and has vertices and edges. Assume is not connected. Then, partition into two nonempty subgraphs and (with and vertices, respectively) such that there are no edges in between vertices from and . Clearly both and are acyclic. If has at most edges and has at most edges, then has at most edges, a contradiction. Therefore, without loss of generality, assume has at least edges. Since is acyclic, the graph obtained by removing enough edges from so that there are only edges left is also acyclic. Now, by the inductive hypothesis, is connected. Therefore, if we add any edge to it will join two vertices that are already connected, and thus form a cycle. Therefore is not acyclic, a contradiction.

*Proposition*: There exists exactly one simple path between each pair of vertices in any tree.

*Proof*: A tree is connected, therefore there exists at least one simple path between each pair of vertices. Suppose there exist two simple paths (or more) between the vertices and , with , namely, and . Let be the least such that equals one of the 's. Clearly such a always exists because and . Let be such that ; since both paths are simple, there is exactly one such . Then consider the sequence of vertices . Clearly no two of the 's are equal, since they are drawn from a simple path; the same is true of the 's. Also, unless or , because of the way was selected. Therefore this sequence of vertices forms a simple cycle, a contradiction.

*Proposition*: Every tree is planar.

*Proof 1*: Since and are not acyclic, neither are any of their subdivisions. Therefore no subdivision of either of these is a subgraph of any tree, as all subgraphs of any tree are acyclic. By Kuratowski's theorem, all trees are therefore planar.

*Proof 2*: It is not difficult to devise an algorithm to generate a planar embedding of a tree. The details are left as an exercise to the reader.

*Theorem*: In a binary tree with external path length , internal path length , and nodes, . (Caution: the statement for -ary trees is *not*, in general, true.)

*Proof*: By induction. For a tree with one node, we have , , and , since the root potentially has two children, each at depth 1. Thus, , as expected. Now, assume that for all binary trees of vertices, where . Then, consider a binary tree of vertices. Choose a leaf of this tree and suppose it is at depth . Remove this from to give the tree with vertices, internal path length , external path length , and nodes. The removal of the leaf node of depth decreases the internal path length by , so . It also removes two external nodes of depth , which decreases the external path length by . But it introduces an external node of depth (where the leaf formerly was), which increases the external path length by , so . By the inductive hypothesis, . Therefore , so .