a) Give a counterexample to the claim in the Theorem. b) Identify the mistake in the...

 

Transcribed Image Text:

a) Give a counterexample to the claim in the Theorem. b) Identify the mistake in the "proof." Theorem. If every vertex in a graph has positive degree, the graph is connected. Proof. We prove by induction on the number of vertices, starting with the case |V| = 2 (the = 1 is vacuous, because if there's only one vertex then it can't have positive degree). If |V|=2 and both vertices have positive degree, then the two vertices have an edge between them and so the graph is connected. For the inductive step, suppose the statement is true for all graphs on n or fewer vertices, and let G be a graph with n vertices such that every vertex of G has positive degree. By the inductive hypothesis, G is connected. Now add a vertex (call it v) to G to obtain a graph with n + 1 vertices (call it H), and assume that v has positive degree so that every vertex in H graph has positive degree. Then v has at least one neighbor (call it u). Thus, vis connected to every other vertex x: we can go from v to u, and then there is a walk from u to x because G was connected. It follows that H is connected, and this completes the proof by induction. a) Give a counterexample to the claim in the Theorem. b) Identify the mistake in the "proof." Theorem. If every vertex in a graph has positive degree, the graph is connected. Proof. We prove by induction on the number of vertices, starting with the case |V| = 2 (the = 1 is vacuous, because if there's only one vertex then it can't have positive degree). If |V|=2 and both vertices have positive degree, then the two vertices have an edge between them and so the graph is connected. For the inductive step, suppose the statement is true for all graphs on n or fewer vertices, and let G be a graph with n vertices such that every vertex of G has positive degree. By the inductive hypothesis, G is connected. Now add a vertex (call it v) to G to obtain a graph with n + 1 vertices (call it H), and assume that v has positive degree so that every vertex in H graph has positive degree. Then v has at least one neighbor (call it u). Thus, vis connected to every other vertex x: we can go from v to u, and then there is a walk from u to x because G was connected. It follows that H is connected, and this completes the proof by induction.