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 sufficientRecitation 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 an￾swers 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.