Tree/Proof of properties of trees - Revision history

Brian at 05:31, 17 May 2011

2011-05-17T05:31:23Z

Brian: right-aligning QED

2011-04-06T21:04:23Z

right-aligning QED

Brian: Created page with "''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..."

2011-04-06T04:47:53Z

Created page with "''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..."

New page

''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.

<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.

<math>_\blacksquare</math>

''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.

<math>_\blacksquare</math>

← Older revision		Revision as of 05:31, 17 May 2011
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>

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