Module 12 Homework Problems
- Let graph \(H\) be defined by the vertex set \(V(H)=\{1,2,3,4,5,6,7,8,9,10\}\) and edge set \(E(H)=\{e_1,…,e_{12}\}\) where each edge is associated with the following endpoints: \(e_1:\{1,5\}\), \(e_2:\{4,6\}\), \(e_3:\{1,1\}\), \(e_4:\{1,1\}\), \(e_5:\{9,10\}\), \(e_6:\{9,10\}\), \(e_7:\{9,1\}\), \(e_8:\{1,3\}\), \(e_9:\{7,8\}\), \(e_{10}:\{5,7\}\), \(e_{11}:\{2,7\}\), \(e_{12}:\{10,5\}\). Draw this graph
- Calculate the degree of every vertex in the graph in problem #1, and calculate the total degree of \(G\).
- Determine whether or not the graphs below are isomorphic, and explain why not it they are indeed not isomorphic.
- Determine whether or not the graphs below are isomorphic, and explain why not if they are indeed not isomorphic.
5. Draw \(K_{12}\); that is, draw the complete graph on \(12\) vertices. (Don’t label the edges)
6. Is there a graph that is \(4\)-partite that is also \(3\)-partite? If there is such a graph, draw it. If not explain why there cant be such a graph.
7. Is every bipartite graph \(3\)-partite? If so, explain why this is the case. If not, find a counterexample.
8. Does there exist a tripartite graph on six vertices with a complete subgraph on four vertices (i.e. a 4-clique)? Either provide an example of such, or explain/prove why no such graph can exist.
9. What is the smallest natural number \(k\) such that \(K_n\) is \(k\)-partite? Please support your answer with an argument. (Hint: when asked a general question, see if you can form a conjecture about the general case based on analyses of simpler tangible examples… and then prove the conjecture!)
10. Does the following graph have an Euler path? If so, find it (writing out the path sequence). If not, explain/prove why not.
11. Does the following graph have an Euler circuit? If so, find it (writing out the path sequence). If not, explain/prove why not
12. Draw an example of a graph that has an Euler path but NOT an Euler circuit. Argue why your graph indeed has an Euler path (without listing the path sequence) but not an Euler circuit.
13. Under what (easy-to-verify) conditions does a graph have an Euler path, but not an Euler circuit?
14. A Hamiltonian Path is a path that passes through each vertex exactly once. Does Every graph with a Hamiltonian Path Also have an Euler Path? If so, explain why. If not, find a counterexample.