1. True, but flawed proof. Every connected graph with n = 1 nodes has at least n - 1 edges. The base case n= 1 holds. Find and explain the errors in the following proofs of the inductive step. a) Consider an arbitrary connected graph Gn with n nodes. By the IH, it has at least n - 1 edges. Add a new node x. To get a connected graph, x must have an edge to at least one node of Gn. Thus, we have at least n - 1 + 1 = n edges, which is our inductive goal. b) Consider an arbitrary graph with n + 1 nodes, and let x be one of them. Since the graph is connected, there must be an edge from x to some other node u. Remove x and the edge to u. The resulting n-node graph is still connected, and by the IH has at least n - 1 edges. With the edge (x, u), the original graph must have had at least n. 1 1. True, but flawed proof. Every connected graph with n = 1 nodes has at least n - 1 edges. The base case n= 1 holds. Find and explain the errors in the following proofs of the inductive step. a) Consider an arbitrary connected graph Gn with n nodes. By the IH, it has at least n - 1 edges. Add a new node x. To get a connected graph, x must have an edge to at least one node of Gn. Thus, we have at least n - 1 + 1 = n edges, which is our inductive goal. b) Consider an arbitrary graph with n + 1 nodes, and let x be one of them. Since the graph is connected, there must be an edge from x to some other node u. Remove x and the edge to u. The resulting n-node graph is still connected, and by the IH has at least n - 1 edges. With the edge (x, u), the original graph must have had at least n. 1