Problem 4: A Graphic Flaw 15 Find a counterexample to the following false claim,

Question

Problem 4: A Graphic Flaw 15 Find a counterexample to the following false claim, and identify the error in the proof Claim 11. For every undirected graph G- (V, E) without loops, if Vl 2 3 and every vertex has a degree of at least 2, there exists a cycle of length 3 Proof. We proceed by induction on IVl. As a base case, consider V- 3. Call the vertices {a, b, cy. Since all vertices have degree 2, then each vertex is connected to both other vertices. Thus abca is a cycle of length 3. As the inductive hypothesis, assume that every graph of k vertices, each of degree at least 2, has a cycle of length 3. To prove the inductive step, let G be a graph with k vertices, each of degree at least 2, and construct a new graph G with k+1 vertices by adding one new vertex to G and 2 edges incident to the new vertex. Since G has k vertices of degree at least 2, by the inductive hypothesis it has a cycle of length 3. Thus the graph G', a graph of k +1 vertices each of degree at least 2, contains the same cycle of length 3. This completes the proof. O

Explanation / Answer

Solution:

The proof is wrong because it is not given if the given undirected graph is a simple graph or an undirected graph, because if it is not a simple graph then it can contain self-loop which means a cycle of length 1, and the vertex can have the degree 2 as well.

In this case, the assumptions are wrong.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---