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

Revision as of 21:04, 6 April 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

@@ Line 7: / Line 7: @@
 * 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.
+* 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>
-<math>_\blacksquare</math>
 ''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.
+''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>
-<math>_\blacksquare</math>
 ''Proposition'': Every tree is planar.
@@ Line 21: / Line 19: @@
 ''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.
+''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>
-<math>_\blacksquare</math>

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

Revision as of 21:04, 6 April 2011

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools