Recitation 8 2)=>(1)Starting from a graph G that satisfies the second definition, we want to show that the following two things must be true 1. G is acyclic We can prove this by conradiction. Suppose that there is a cycle in G, and take any pair (u, u)of vertices in the cycle. Since we are in a cycle, we know that there's a path pi connecting u to u and another, different path p2 connecting v to u. But then taking path p2 in reverse would take us from u to u, which contradicts the assumption that theres a unique path connecting every pair of vertices. Therefore we conclude that g must be acyclic 2. G has n-1 edges. We know that G is a connected graph and above we showed that it must also be acyclic. In class we showed that an acyclic graph with n vertices needs at least n-1 edges to be connected. We now need to prove that it can have at most n-1 edges(otherwise, it will not be acyclic). The proof is by induction on n Base case: For n=0 and n= l, a connected, acyclic graph can have at most n-1 nductive step: Assume that all connected, acyclic graphs with n vertices or less have n-1 edges. Consider a connected, acyclic graph G with n 1 vertices Remove a vertex v along with all incident edges. This will create k> 1 connected components. Each connected component is connected(by definition) and acyclic (since G was acyclic). Therefore by our induction hypothesis, the ith connected component (1<i<k) can have at most Vl-1 edges. Thus the total number of edges will be at most n-k. Now, we bring back the vetex we removed along with all its incident edges. Notice that since G is acyclic, the vertex cannot be connected to each component with more than one edges. This means that the number of new edges is at most h, which brings our total number of edges to at most n-k+k=n Thus. the claim holds for g as well Zthe case k= 1 corresponds to the situation in which the removal of the vertex leaves us with a connected subgraph(one piece) If there were two edges connecting the vertex to a connected component, we could go from the vertex to the connected component through the first edge then find a path to the second connection point [guar anteed to exist b/c we are in a connected component] and return to the original vertex through the second ge. This would contradict the assumption that our original graph was acyclicRecitation 8 2 (2) =⇒ (1)Starting from a graph G that satisfies the second definition,we want to show that the following two things must be true: 1. G is acyclic We can prove this by conradiction. Suppose that there is a cycle in G, and take any pair (u, v) of vertices in the cycle. Since we are in a cycle, we know that there’s a path p1 connecting u to v and another, different path p2 connecting v to u. But then taking path p2 in reverse would take us from u to v, which contradicts the assumption that there’s a unique path connecting every pair of vertices. Therefore, we conclude that G must be aclyclic. 2. G has n − 1 edges. We know that G is a connected graph and above we showed that it must also be acyclic. In class we showed that an acyclic graph with n vertices needs at least n − 1 edges to be connected. We now need to prove that it can have at most n − 1 edges (otherwise, it will not be acyclic). The proof is by induction on n. Base case: For n =0 and n = 1, a connected, acyclic graph can have at most n − 1 edges. Inductive step: Assume that all connected, acyclic graphs with n vertices or less have ≤ n − 1 edges. Consider a connected, acyclic graph G with n +1 vertices. Remove a vertex v along with all incident edges. This will create k ≥ 1 connected components2. Each connected component is connected (by definition) and acyclic (since G was acyclic). Therefore by our induction hypothesis, the ith connected component (1 ≤ i ≤ k) can have at most |Vi| − 1 edges. Thus the total number of edges will be at most n − k. Now, we bring back the vetex we removed along with all its incident edges. Notice that since G is acyclic, the vertex cannot be connected to each component with more than one edges3. This means that the number of new edges is at most k, which brings our total number of edges to at most n − k + k = n. Thus, the claim holds for G as well. 2the case k =1 corresponds to the situation in which the removal of the vertex leaves us with a connected subgraph (one piece) 3If there were two edges connecting the vertex to a connected component, we could go from the vertex to the connected component through the first edge, then find a path to the second connection point [guar￾anteed to exist b/c we are in a connected component] and return to the original vertex through the second edge. This would contradict the assumption that our original graph was acyclic