Question

Find the logical mistakes in these proofs, and explain why the mistakes youve identified cause problems in their arguments.(b)Claim: Suppose that G is a graph on n 3 vertices in which the degree of every vertex is exactly 2. Then G is a cycle Proof

Find the logical mistakes in these proofs, and explain why the mistakes you've identified cause problems in their arguments.
(b)Claim: Suppose that G is a graph on n 3 vertices in which the degree of every vertex is exactly 2. Then G is a cycle Proof. We proceed by induction on n, the number of vertices in G. Our base case is simple: for n - 3, the only graph with 3 vertices in which all vertices have degree 2 is Cs, which is a cycle. is: we assume if G is a graph on n vertices in which every vertex has degree 2 then G is a cycle. Using this, we want to prove our claim for n +1: that is, we want to take any graph G on n+1 vertices in which every vertex has degree 2, and show that G must also be a cycle. Doing this is straightforward! Just take any edge (x, y E G, and perform edge contraction2 on this edge. The result is a graph on n vertices, in which all vertices still have degree 2; therefore, by our inductive assumption, this contracted graph was already a cycle. Now, undo this contraction! This extends our graph to a cycle that's longer by one edge. In particular, it means that our original graph was a cycle, as desired.
0 0
Add a comment Improve this question Transcribed image text
Answer #1

Performing and edge contraction of the graph comprising of two copies of C_3 (two triangles) we get a graph comprising of one triangle and one K_2 copy. The original graph had all vertices having degree 2 but the new graph has vertices with degree 1. So the induction step is not valid for disconnected graphs

Add a comment
Know the answer?
Add Answer to:
Find the logical mistakes in these proofs, and explain why the mistakes you've identified cause problems in their a...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT