this is my question Let\'s say that a graph has \"two ends\" if it has exactly t
ID: 3533421 • Letter: T
Question
this is my question
Let's say that a graph has "two ends" if it has exactly two vertices of degree 1 and all its other vertices have degree 2. For example, here is one such graph: A line graph is a graph whose vertices can be listed in a sequence with edges between consecutive vertices only. So the two-ended graph above is also a line graph of length 4. Prove that the following theorem is false by drawing a counterexample. False Theorem. Every' two-ended graph is a line graph. Point out the first erroneous statement in the following bogus proof of the false theorem and describe the error. Bogus proof. We use induction. The induction hypothesis is that every two-ended graph with n edges is a path. Base case (n = 1): The only two-ended graph with a single edge consists of two vertices joined by an edge: Sure enough, this is a line graph. Inductive case: We assume that the induction hypothesis holds for some n >= 1 and prove that it holds for n + 1. Let Gn be any two-ended graph with n edges. By the induction assumption, Gn is a line graph. Now suppose that we create a two-ended graph Gn+i by adding one more edge to Gn. This can be done in only one way: the new edge must join an endpoint of Gn to a new vertex; otherwise, Gn+i would not be two-ended. Clearly, Gn+1 is also a line graph. Therefore, the induction hypothesis holds for all graphs with n + 1 edges, which completes the proof by induction.Explanation / Answer
Counter example?a graph with two connected component: one component is two vertices and one edge, the other is a cycle.
The proof is wrong because it only proves each line graph is two-end. To prove P(n+1) you need to prove every possible graph, not just line graph.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.