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

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

@@ 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/>
 <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>

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

Latest revision as of 05:31, 17 May 2011

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools