Difference between revisions of "Tree/Proof of properties of trees"

From PEGWiki
Jump to: navigation, search
m (right-aligning QED)
 
Line 21: Line 21:
 
''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/>
 
''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>
 
<div align="right"><math>_\blacksquare</math></div>
 +
 +
''Theorem'': In a binary tree with external path length <math>E</math>, internal path length <math>I</math>, and <math>N</math> nodes, <math>E = I + 2N</math>. (Caution: the statement <math>E = I + kN</math> for <math>k</math>-ary trees is ''not'', in general, true.)
 +
 +
''Proof'': By induction. For a tree with one node, we have <math>I = 0</math>, <math>N = 1</math>, and <math>E = 2</math>, since the root potentially has two children, each at depth 1. Thus, <math>E = I + 2N</math>, as expected. Now, assume that <math>E = I + 2(N-1)</math> for all binary trees of <math>N-1</math> vertices, where <math>N \geq 2</math>. Then, consider a binary tree <math>T</math> of <math>N</math> vertices. Choose a leaf of this tree and suppose it is at depth <math>d</math>. Remove this from <math>T</math> to give the tree <math>T'</math> with <math>N-1</math> vertices, internal path length <math>I'</math>, external path length <math>E'</math>, and <math>N-1</math> nodes. The removal of the leaf node of depth <math>d</math> decreases the internal path length by <math>d</math>, so <math>I' = I - d</math>. It also removes two external nodes of depth <math>d+1</math>, which decreases the external path length by <math>2(d+1)</math>. But it introduces an external node of depth <math>d</math> (where the leaf formerly was), which increases the external path length by <math>d</math>, so <math>E' = E - 2(d+1) + d = E - d - 2</math>. By the inductive hypothesis, <math>E' = I' + 2(N-1)</math>. Therefore <math>E - d - 2 = I - d + 2N - 2</math>, so <math>E = I+2N</math>.<div align="right"><math>_\blacksquare</math></div>

Latest revision as of 05:31, 17 May 2011

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