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 $V-1$ vertices (where $V \geq 2$). We show it holds for all graphs with $V$ vertices:

• Suppose a simple graph $G$ has $V$ vertices and it is connected and acyclic. Choose any vertex $u$. Clearly $u$ has degree at least one, since the graph is connected. If $u$ has degree one, stop. If not, choose any edge incident upon $u$ and denote the other endpoint $v$. If $v$ has degree one, stop; otherwise choose a different edge out of $v$ and denote the other endpoint $w$; 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 $G'$ be $G$ minus this vertex and its single incident edge. Clearly $G'$ is still connected and acyclic and has $V-1$ vertices; therefore it has $V-2$ edges by the inductive hypothesis. Therefore $G$ has $V-1$ edges.
• Suppose a simple graph $G$ has $V$ vertices, is connected, and has $V-1$ 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 $2V$, so, by the handshake lemma, there are at least $V$ vertices, a contradiction; therefore at least one vertex must have degree one. Let $G'$ be the graph obtained by removing this vertex and its incident edge from $G$. Then $G'$ is still connected and it has $V-1$ vertices and $V-2$ edges; by the inductive hypothesis, it is acyclic. Adding a single vertex and connecting it via a single edge to regenerate $G$ clearly does not introduce any cycles.
• Suppose a simple graph $G$ is acyclic and has $V$ vertices and $V-1$ edges. Assume $G$ is not connected. Then, partition $G$ into two nonempty subgraphs $G_1$ and $G_2$ (with $V_1$ and $V_2$ vertices, respectively) such that there are no edges in $G$ between vertices from $G_1$ and $G_2$. Clearly both $G_1$ and $G_2$ are acyclic. If $G_1$ has at most $V_1-1$ edges and $G_2$ has at most $V_2-1$ edges, then $G$ has at most $V_1 + V_2 - 2 = V - 2$ edges, a contradiction. Therefore, without loss of generality, assume $G_1$ has at least $V_1$ edges. Since $G_1$ is acyclic, the graph $G_1'$ obtained by removing enough edges from $G_1$ so that there are only $V_1-1$ edges left is also acyclic. Now, by the inductive hypothesis, $G_1'$ is connected. Therefore, if we add any edge to $G_1'$ it will join two vertices that are already connected, and thus form a cycle. Therefore $G_1$ is not acyclic, a contradiction.
  

$_\blacksquare$

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 $u$ and $v$, with $u \neq v$, namely, $u = s_0, s_1, \ldots, s_m = v$ and $v = t_0, t_1, \ldots, t_n = v$. Let $p$ be the least $i > 0$ such that $s_p$ equals one of the $t$'s. Clearly such a $p$ always exists because $s_m = t_n$ and $m > 0$. Let $q$ be such that $s_p = t_q$; since both paths are simple, there is exactly one such $q$. Then consider the sequence of vertices $u = s_0, s_1, \ldots, s_p = t_q, t_{q-1}, \ldots, t_0 = u$. Clearly no two of the $s$'s are equal, since they are drawn from a simple path; the same is true of the $t$'s. Also, $s_i \neq t_j$ unless $i = p, j = q$ or $i = 0, j = 0$, because of the way $p$ was selected. Therefore this sequence of vertices forms a simple cycle, a contradiction.

$_\blacksquare$

Proposition: Every tree is planar.

Proof 1: Since $K_5$ and $K_{3,3}$ 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.

$_\blacksquare$

Theorem: In a binary tree with external path length $E$, internal path length $I$, and $N$ nodes, $E = I + 2N$. (Caution: the statement $E = I + kN$ for $k$-ary trees is not, in general, true.)

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

$_\blacksquare$