Editing Tree/Proof of properties of trees
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| 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 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> 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. |
| − | + | ||
| + | <math>_\blacksquare</math> | ||
''Proposition'': There exists exactly one simple path between each pair of vertices in any tree. | ''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. |
| − | + | ||
| + | <math>_\blacksquare</math> | ||
''Proposition'': Every tree is planar. | ''Proposition'': Every tree is planar. | ||
| Line 19: | Line 21: | ||
''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 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. |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | <math>_\blacksquare</math> | |
