Discrete math worksheet

Math 210, Concepts from Discrete Mathematics Worksheet 8 This is a video handout. 1) Write the definition of isomorphism between two simple undirected graphs. 2) Draw the graph 𝐾4 , label all its vertices, then write its adjacency matrix. 3) Draw a simple connected bipartite graph 𝐺 = (𝑉, 𝐸) such that its bipartition 𝑉1 , 𝑉2 has |𝑉1 | = 5 and |𝑉2 | = 4 and deg(𝑎) ≤ 3 for all 𝑎 ∈ 𝑉 . How many 1's does the incidence matrix have in it? No need to justify. 4) Let 𝐺 = (𝑉, 𝐸) be a graph with 𝑛 vertices and 𝑚 edges with no loops. How many 1's does the incidence matrix have in it? Justify your answer. 5) Draw a connected bipartite graph 𝐺 = (𝑉, 𝐸) such that its bipartition 𝑉1 , 𝑉2 has |𝑉1 | and |𝑉2 | = 4 and deg(𝑎) ≤ 3 for all 𝑎 ∈ 𝑉 . =5 a) Determine how many cut vertices and how many cut edges G has. b) How many 1's does the incidence matrix have in it? c) Does your graph have an Euler path? Justify your answer. 6) Let G be a simple connected graph with exactly 8 vertices, one of them has degree 7, and the other 7 vertices have degree 3. Is G isomorphic to 𝑊7 ? Justify your answer. 7) Draw a simple connected graph with 6 vertices and 6 edges which is NOT isomorphic to 𝐶6 . a) Determine how many cut vertices and how many cut edges G has. b) Does your graph have an Euler path? Justify your answer. 8) Determine for which 𝑛 ≥ 3, 𝑊𝑛 has a Hamilton circuit. Justify your answer. 9) Consider the following graph: Label all the vertices and edges. Determine whether the graph has a Hamilton path. Determine whether the graph has a Hamilton circuit. Justify your answers. 10) Draw a connected simple graph with an Euler circuit but without a Hamiltonian path. Then show that your graph has an Euler circuit but it does not have a Hamiltonian path. ...