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

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

''Proposition'': Every tree is planar.

''Proof 1'': Since <math>K_5</math> and <math>K_{3,3}</math> 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.<br/>
<div align="right"><math>_\blacksquare</math></div>