Graph ti resulting graph G. By the induction assumption, G has at least VI-n connected com ponents. Now add back the edge u-v to obtain the original graph G. If u and v were in the same connected component of G, then g has the same number of connected compo- nents as G, which is at least V-n. Otherwise, if u and v were in different connected components of G, then these two components are merged into one in G, but all other components remain. Therefore, G has at least n-1=V-(n+ 1)connected components The theorem follows by induction Corollary 2. Every connected graph with n vertices has at least n-1 edge A couple points about the proof of Theorem 1 are worth noting. First, notice that we used induction on the number of edges in the graph. This is very common in proofs involving graphs, and so is induction on the number of vertices. When you're pi resen with a graph problem, these two approachs should be among the first you consider. Dont try induction on other variables that crop up in the problem unless these two strategies seem hopeless The second point is more subtle. Notice that in the inductive step, we took an arbitrary (n 1)-edge graph, threw out an edge so that we could apply the induction assumption, and then put the edge back. You'll see this shrink-down, grow-back process very often in the inductive steps of proofs related to graphs. This might seem like needless effort; why not start with an n-edge graph and add one more to get an(n+ 1-edge graph? That would work fine in this case but opens the door to a very nasty logical error in similar arguments. (You'll see an example in recitation. Always use shrink-down, grow-back arguments, and you'll never fall into this trap 2.2 Distance and Diameter The distance between two vertices in a graph is the length of the shortest path between them. For example, the distance between two vertices in a graph of airline connections is the minimum number of flights required to travel between two citiesGraph Theory 9 resulting graph G� . By the induction assumption, G� has at least |V | − n connected com￾ponents. Now add back the edge u—v to obtain the original graph G. If u and v were in the same connected component of G� , then G has the same number of connected compo￾nents as G� , which is at least |V | − n. Otherwise, if u and v were in different connected components of G� , then these two components are merged into one in G, but all other components remain. Therefore, G has at least |V | − n − 1 = | | V − (n + 1) connected components. The theorem follows by induction. Corollary 2. Every connected graph with n vertices has at least n − 1 edges. A couple points about the proof of Theorem 1 are worth noting. First, notice that we used induction on the number of edges in the graph. This is very common in proofs involving graphs, and so is induction on the number of vertices. When you’re presented with a graph problem, these two approachs should be among the first you consider. Don’t try induction on other variables that crop up in the problem unless these two strategies seem hopeless. The second point is more subtle. Notice that in the inductive step, we took an arbitrary (n + 1)­edge graph, threw out an edge so that we could apply the induction assumption, and then put the edge back. You’ll see this shrink­down, grow­back process very often in the inductive steps of proofs related to graphs. This might seem like needless effort; why not start with an n­edge graph and add one more to get an (n + 1)­edge graph? That would work fine in this case, but opens the door to a very nasty logical error in similar arguments. (You’ll see an example in recitation.) Always use shrink­down, grow­back arguments, and you’ll never fall into this trap. 2.2 Distance and Diameter The distance between two vertices in a graph is the length of the shortest path between them. For example, the distance between two vertices in a graph of airline connections is the minimum number of flights required to travel between two cities. A B C D E F G H