What is wrong with the following proof? Statement: If every node in a graph has degree at least 1 , then the graph is connected. Proof. We use induction. Let P(n) be the proposition that if every node in an n-node graph has degree at least 1, then the graph is connected. Base case: There is only one graph with a single node and it has degree 0 . Therefore, P(1) is vacuously true. Inductive step: Fix k1 and suppose that P(n) is true for n=1,,k. Consider an k-node graph G in which every node has degree at least 1. By the induction hypothesis, G is connected; that is, there is a path between every pair of vertices. Now we add one more node x to G to obtain an (k+1) node graph H. Since x must have degree at least one, there is an edge from x to some other node; call it y. Since y is connected to every other node in the graph, x will be connected to every other node in the graph. QED (a) The proof should instead induct on the degree of each node. (b) The inductive step fails to conisder (k+1)-node graphs which cannot be constructed by (b) adding a node to G. (c) This is a trick question - there is nothing wrong with the proof. (d) Since there aren't any 1-node graphs where node degrees are 1, the proof must also consider a second base case (n=2). (e) Since there aren't any 1-node graphs where node degrees are 1,P(1) is actually false. (f) The inductive step fails to conisder (k+1)-node graphs where some vertices have degree 0