6.042/18.062J Mathematics for Computer Science farch 2. 2005 Srini devadas and eric Lehman Notes for recitation 8 1 Graphs and Trees The following two definitions of a tree are equivalent Definition 1: A tree is an acyclic graph of n vertices that has n-1 edges Definition 2: A tree is a connected graph such that Vu, v E V, there is a unique path connecting u to u. In general, when we want to show the equivalence of two definitions, we must show that if the first definition is met, so is the second, and vice versa. (1)=(2) Suppose that G is an acyclic graph with E=V-1. We need to demonstrate the following two facts 1. There is a unique path connecting any pair of vertices. The proof is by contradic- tion. Suppose that there exists a pair of vertices(u, u) with two distinct paths pi and P2 connecting u to v. In more"graphic"terms, we have u v and u 2 u. Let p2 be the reverse of path p2(which takes us from v to u). Then u v 4 u is a cycle from u back to u, which contradicts the fact that G is an acyclic graph. Therefore, we conclude that there exists a unique path between any two pairs of vertices 2. G is connected. We want to prove that an acyclic graph G with n vertices and n-1 edges is connected. The proof is by induction on the number of vertices of G. Base case: For n= l and n= 2 the claim holds, since in both cases, a graph with n-1 edges is connected. Inductive step: Assume that the claim is true for all graphs up to size n. Consider an acyclic graph G with n+1 vertices and n edges. At least one of the vertices must have degree 1(see note ) Now take that vertex of degree 1 and remove it, along with the associated edge. The graph G that remains has n vertices and n-1 edges and is connected according to our induction hypothesis We then restore the vertex we removed to get back to G and notice that G must als be connected because the subgraph G" is connected, and the vertex v we just took out is connected to the subgraph through its edge Since there are n edges, the sum of the degrees of the vertices is 2n. There are n+I vertices, which means that at least one vertex must have degree either 0 or 1 (if they all had degree 2 or more, the sum of the degrees would be> 2n+ 2). The 0-degree vertex is actually imposible, because the subgraph of n ertices would have n edges, and this would create a cycle(see the second inductive proof. Therefore, at least one vertex has to have degree exactly 1
6.042/18.062J Mathematics for Computer Science March 2, 2005 Srini Devadas and Eric Lehman Notes for Recitation 8 1 Graphs and Trees The following two definitions of a tree are equivalent. Definition 1: A tree is an acyclic graph of n vertices that has n − 1 edges. Definition 2: A tree is a connected graph such that ∀u, v ∈ V , there is a unique path connecting u to v. In general, when we want to show the equivalence of two definitions, we must show that if the first definition is met, so is the second, and vice versa. (1) =⇒ (2) Suppose that G is an acyclic graph with |E| = |V | − 1. We need to demonstrate the following two facts: 1. There is a unique path connecting any pair of vertices. The proof is by contradiction. Suppose that there exists a pair of vertices (u, v) with two distinct paths p1 and p1 p2 ← p2 connecting u to v. In more “graphic” terms, we have u � v and u � v. Let p2 ← p1 p2 be the reverse of path p2 (which takes us from v to u). Then u � v � u is a cycle from u back to u, which contradicts the fact that G is an acyclic graph. Therefore, we conclude that there exists a unique path between any two pairs of vertices. 2. G is connected. We want to prove that an acyclic graph G with n vertices and n − 1 edges is connected. The proof is by induction on the number of vertices of G. Base case: For n =1 and n =2 the claim holds, since in both cases, a graph with n−1 edges is connected. Inductive step: Assume that the claim is true for all graphs up to size n. Consider an acyclic graph G with n +1 vertices and n edges. At least one of the vertices must have degree 1 (see note 1). Now take that vertex of degree 1 and remove it, along with the associated edge. The graph G that remains has n vertices and n − 1 edges and is connected according to our induction hypothesis. We then restore the vertex we removed to get back to G and notice that G must also be connected because the subgraph G is connected, and the vertex v we just took out is connected to the subgraph through its edge. 1Since there are n edges, the sum of the degrees of the vertices is 2n. There are n +1 vertices, which means that at least one vertex must have degree either 0 or 1 (if they all had degree 2 or more, the sum of the degrees would be ≥ 2n + 2). The 0-degree vertex is actually imposible, because the subgraph of n vertices would have n edges, and this would create a cycle (see the second inductive proof). Therefore, at least one vertex has to have degree exactly 1.
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 acyclic
Recitation 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 [guaranteed 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
Recitation 8 3 Rules: Teams take questions in cyclic order. Each team has 15 seconds to answer. A correct answer is worth 1 point. If a team can not answer a question correctly, the question goes to the next team. If no team can answer, the ta gets a point and provides the answer This test is open book. Between problems, the game may stop for questions. The TA can change the rules in any way he or she sees fit at any time Here is a picture of a graph G=(V,E) E (The edge E-D is absent initially, but will be added later. 1. What are the elements of v called? vertices 2. What are the elements of E called? Edges 3. What are the elements of V in this case? A, B, C, D, E, Fl 4. What are the elements of E in this case?(A-B, A-C, B-C, B-D,C-D,E-FI 5. Is this graph connected? No 6. What is the definition of connected, anyway? a graph is connected if there is a path between every pair of vertices 7. What is a connected component of a graph? A maximal, connected subgraph. Here, maximal means that including any more vertices would yield a disconnected sub- graph 8. What are the connected components of this graph? The subgraph consisting of vertices E and F and the edge between them The subgraph consisting of vertices A, B, C, and D and the edges between them 9. Now suppose we add the edge E-D Is the graph connected now? Yes 10. What is the distance between a and D? 2
Recitation 8 3 Rules: Teams take questions in cyclic order. Each team has 15 seconds to answer. A correct answer is worth 1 point. If a team can not answer a question correctly, the question goes to the next team. If no team can answer, the TA gets a point and provides the answer. This test is open book. Between problems, the game may stop for questions. The TA can change the rules in any way he or she sees fit at any time. Here is a picture of a graph G = (V,E). A B C D E F (The edge E—D is absent initially, but will be added later.) 1. What are the elements of V called? Vertices. 2. What are the elements of E called? Edges. 3. What are the elements of V in this case? {A, B, C, D, E, F} 4. What are the elements of E in this case? {A—B,A—C, B—C, B—D, C—D, E—F} 5. Is this graph connected? No. 6. What is the definition of connected, anyway? A graph is connected if there is a path between every pair of vertices. 7. What is a connected component of a graph? A maximal, connected subgraph. Here, maximal means that including any more vertices would yield a disconnected subgraph. 8. What are the connected components of this graph? • The subgraph consisting of vertices E and F and the edge between them. • The subgraph consisting of vertices A, B, C, and D and the edges between them. 9. Now suppose we add the edge E—D. Is the graph connected now? Yes. 10. What is the distance between A and D?2
Recitation 8 11. How is the distance between vertices and y defined? It is the length of the shortest path between r and 12. What is the diameter of this graph? 4 13. How is diameter defined? It is the distance between the farthest pair of vertices. (A ind F in this case.) 14. Is this a tree? no 15. What is a tree, anyway? A connected, acyclic graph.(However, there are many other quivalent ways to characterize a tree and any one could be taken as the definition. 16. How many different cycles are there? Three. One with vertices A, B, C, one with vertices. B C. D and one with vertices A B. C. and D 17. What's a spanning tree of this graph? There are several; one is the subgraph with vertices A through F and edges A-B, B-C, B-D, E-D, and E-F. Later an- swers assume this one 18. What is a spanning tree of a graphG=(V, E)anyhow? A tree with vertex set I and edge set ECE 19. Does every graph have a spanning tree? No, but every connected graph does 20. For the remaining questions, let's focus on that spanning tree. Which vertices are the leaves of this tree? A C. and F 21. Does there exist a tree with the same number of vertices but a different number of edges? No. For every tree, V=EI+1 22. Does there exist a tree with the same number of vertices but a different number of leaves-yes or no? Yes 23. What's an example of a 6-vertex tree NOT isomorphic to the spanning tree? One example is a path of length 5 24. What exactly does it mean for two graphs to be isomorphic? There is a a one-to-one correspondence between the vertices in the two graphs such that there is an edge between two vertices in the first graph if and only if there is an edge between the two corresponding vertices in the second graph. 5. How can you prove this spanning tree is not isomorphic to the one two questions back? In general, the simplest way is to identify some distinguishing property, such as the number of vertices, number of edges, number of leaves, or pattern of vertex degrees. Any argument along these lines is sufficient
Recitation 8 4 11. How is the distance between vertices x and y defined? It is the length of the shortest path between x and y. 12. What is the diameter of this graph? 4 13. How is diameter defined? It is the distance between the farthest pair of vertices. (A and F in this case.) 14. Is this a tree? No. 15. What is a tree, anyway? A connected, acyclic graph. (However, there are many other equivalent ways to characterize a tree and any one could be taken as the definition.) 16. How many different cycles are there? Three. One with vertices A, B, C, one with vertices, B, C, D, and one with vertices A, B, C, and D. 17. What’s a spanning tree of this graph? There are several; one is the subgraph with vertices A through F and edges A—B, B—C, B—D, E—D, and E—F. Later answers assume this one. 18. What is a spanning tree of a graph G = (V,E) anyhow? A tree with vertex set V and edge set E ⊆ E. 19. Does every graph have a spanning tree? No, but every connected graph does. 20. For the remaining questions, let’s focus on that spanning tree. Which vertices are the leaves of this tree? A, C, and F 21. Does there exist a tree with the same number of vertices, but a different number of edges? No. For every tree, |V | = |E| + 1. 22. Does there exist a tree with the same number of vertices, but a different number of leaves— yes or no? Yes. 23. What’s an example of a 6-vertex tree NOT isomorphic to the spanning tree? One example is a path of length 5. 24. What exactly does it mean for two graphs to be isomorphic? There is a a one-to-one correspondence between the vertices in the two graphs such that there is an edge between two vertices in the first graph if and only if there is an edge between the two corresponding vertices in the second graph. 25. How can you prove this spanning tree is not isomorphic to the one two questions back? In general, the simplest way is to identify some distinguishing property, such as the number of vertices, number of edges, number of leaves, or pattern of vertex degrees. Any argument along these lines is sufficient.