1. An undirected graph is said to be connected iff every pair of vertices in the...

Transcribed Image Text:

1. An undirected graph is said to be connected iff every pair of vertices in the graph are reachable from one another. Prove the following statement: Any connected undirected graph with n nodes has at least (n-1) edges. We will prove the statement using Mathematical Induction. The first step in such a proof is to define the propositional function. Fortunately for this problem, this is already given in the statement of the claim. P(n): Any connected undirected graph with n nodes has at least (n-1) edges. The base case is simple. P(1) holds since any connected graph with 1 node having at least 0 edges, is indeed true. For the inductive step, we assume that P (1), P(2), ..., P(k) holds for an arbitrary k ≥ 1, and then we will show that P(k+1) holds. Consider any connected graph G with (k+1) nodes and k edges. You are asked to complete the argument by doing the following case analysis: (a) (10 points) Show that if the degrees of all nodes in G is at least 2, then G has at least k edges. (b) (10 points) Consider the case where there exists a node v with degree 1 in G. In this case, consider the graph G' obtained from G by removing vertex v and its edge. Now use the induction assumption on G' to conclude that G has at least k edges. 1. An undirected graph is said to be connected iff every pair of vertices in the graph are reachable from one another. Prove the following statement: Any connected undirected graph with n nodes has at least (n-1) edges. We will prove the statement using Mathematical Induction. The first step in such a proof is to define the propositional function. Fortunately for this problem, this is already given in the statement of the claim. P(n): Any connected undirected graph with n nodes has at least (n-1) edges. The base case is simple. P(1) holds since any connected graph with 1 node having at least 0 edges, is indeed true. For the inductive step, we assume that P (1), P(2), ..., P(k) holds for an arbitrary k ≥ 1, and then we will show that P(k+1) holds. Consider any connected graph G with (k+1) nodes and k edges. You are asked to complete the argument by doing the following case analysis: (a) (10 points) Show that if the degrees of all nodes in G is at least 2, then G has at least k edges. (b) (10 points) Consider the case where there exists a node v with degree 1 in G. In this case, consider the graph G' obtained from G by removing vertex v and its edge. Now use the induction assumption on G' to conclude that G has at least k edges.