search the text name on the Google for book

Show written solutions for all of the following problems. Unit 7: Graph Theory Text: Discrete Mathematics: An Open Introduction, 3"I Edition. 4.1 Definitions 1) a) Is it possible for two different (non-isomorphic) graphs to have the same number of vertices and the same number of edges? b) What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2,2, 3, and 4, for example)? Both situations are possible. Draw two such graphs for both cases. 4.3 Planar Graphs 2) Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6? Prove your answer. Hint: You can use the Handshake Lemma to find the number of edges, in terms of v, the number of vertices. 4.5 Euler Paths and Circuits 3) On the table rests 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be? Draw a graph with 6 vertices and 8 edges. What sort of path would be appropriate? Text: Applied Discrete Structures 9.1: Graphs General Introduction 4) Draw complete undirected graphs with 1, 2, 3, 4, and 5 vertices. How many edges does Kn, a complete undirected graph with n vertices, have? 5) a) How many edges does a complete tournament graph with n vertices have? b) How many edges does a single-elimination tournament graph with n vertices have? 6) Determine whether the graphs pictured below in Graph 1 and Graph 2 are isomorphic. If the graphs are isomorphic, describe an isomorphism between them. If the graphs are not isomorphic, give at least two properties that are preserved under isomorphism such that one graph has the property, but the other does not. For at least one of these properties you choose, prove that it is indeed preserved under isomorphism (you only need prove one of them). 3:46 PM Tue May 2 .. . 88% d21.oakton.edu A other does not. For at least one of these properties you choose, prove that it is indeed preserved under isomorphism (you only need prove one of them). Graph 1 Graph 2 9.3: Connectivity 7) Apply Algorithm 9.3.2 Breadth-first Search to find a path from 5 to 1 in Figure 9.3.1. What would be the final value of V and D? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order, as we assumed in Example 9.3.1. Note: In Example 9.3.1, the value of 4 in the Depthset row, under k = 3, means there are 4 edges traversed to arrive at vertex 3 from vertex 2.Figure 9.3.1 9.5: Graph Optimization 8) Use Algorithm 9.5.1 The Closest Neighbor Algorithm to find the closest neighbor circuit and cost starting at vertex 3 in Figure 1. Note: This graph is not complete, but we can still use the algorithm provided by choosing the edges that allow a circuit. In the case where you arrive at a "dead-end", use backtracking to attempt an alternate closest neighbor until you can find a circuit. 2 1 . 4-K; Figure 1 4:02 PM Tue May 2 no. d2|.oakton.edu ii Unit 8: Tree Theory Text: Discrete Mathematics: An Open Introduction, 3'rj Edition. 4.2 Trees 1) Prove that any graph (not necessarily a tree) with v vertices and e edges that satisfies v > e + 1 will NOT be connected. Hint: Try a proof by contradiction and consider a spanning tree of the graph, 2) Prove using reverse induction that every tree with n vertices is bipartite, Hint: You will need to remove a vertex of degree one, apply the inductive hypothesis to the result, and then say which set the degree one vertex belongs to. 3) Given Graph 3 below, how many different spanning trees are there? Hint: Use SageMath. We must use numbers instead of letters for the vertex labels. Graph 3 Text: Applied Discrete Structures 10.1: What is a Tree? 4) a) Prove that if G = (V, E) is a tree and e E E, then (V, E {e}) is a forest of two trees. b) Prove that if (V1, E1) and (V2, E2) are disjoint trees and e is an edge that connects a vertex in V1 to a vertex in V2, then (V1 U V2, E1 U E2 U {e}) is a tree. 10.2: Spanning Trees 5) Use Prim's Algorithm to find a minimal spanning tree for the following graphs and calculate the cost associated. Start at vertex A. 3) Tue May 2 I. o d2l.oakton.edu ii 10.3: Rooted Trees 6) Use Kruskal's algorithm to find a minimal spanning tree for the following graph and calculate the cost associated. In addition to the spanning tree, find the final rooted tree in the algorithm. When you merge two trees in the algorithm, make the root with the lower number the root of the new tree.