Graph isomorphism

2

1. Draw three mathematically different graphs, labelled graph \(A\), graph \(B\) and graph \(C\), each with four vertices, of orders 1, 3, 3 and 3, and five arcs.
2. Explain how you know that none of the graphs from part (i) is Eulerian.

2 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. List the vertex degrees for each graph.
2. Prove that the graphs are non-isomorphic. The two graphs are joined together by adding an arc connecting J and T .
3. 1. Explain how you know that the resulting graph is not Eulerian.
   2. Describe how the graph can be made Eulerian by adding one more arc. The vertices of the graph \(K _ { 3 }\) are connected to the vertices of the graph \(K _ { 4 }\) to form the graph \(K _ { 7 }\).
4. Explain why 12 arcs are needed connecting \(K _ { 3 }\) to \(K _ { 4 }\).

1 There are six non-isomorphic trees with exactly six vertices.
A student has drawn the diagram below showing six trees each with exactly six vertices. However, two of the trees that the student has drawn are isomorphic. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Identify which two of these trees are isomorphic.
2. Draw an example of the missing tree. Graph G has exactly six vertices.
   The degree sequence of G is \(1,1,1,3,3,3\).
3. Without using a sketch, calculate the number of edges in graph G.
4. Explain how the result from part (c) shows that graph G is not a tree. In a simple graph with six vertices each vertex degree must be one of the values \(0,1,2,3,4\) or 5 .
5. Use the pigeonhole principle to show that in a simple graph with six vertices there must be at least two vertices with the same vertex degree.

1 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Prove that the graphs are isomorphic.
   2. Verify that Euler's formula holds for graph G1.
2. Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
3. Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.

4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 A tree, T , has exactly six nodes. The degrees of the six nodes of T are
1
2 \(( 4 - x )\) \(( 2 x - 5 )\) \(( 4 x - 11 )\) \(( 3 x - 5 )\) where \(x\) is an integer.
(b) Explain how you know that T cannot be Eulerian.
(c) (i) Determine the value of \(x\) (ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.
(5) \includegraphics[max width=\textwidth, alt={}, center]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-07_588_579_977_744} \section*{Figure 2} Figure 2 shows a graph, \(G\), with six nodes with degrees \(1,2,3,3,3\) and 4
(d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees \(1,2,3,3,3\) and 4 that is not isomorphic to G .

2 Two simply connected graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Write down the orders of the vertices for each of these graphs.
   2. How many ways are there to allocate these vertex degrees to a graph with vertices \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T }\) and U ?
   3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
2. Show that graphs 1 and 2 are not isomorphic.
3. 1. Write down a Hamiltonian cycle for graph 1.
   2. Use Euler's formula to determine the number of regions for graph 1.
   3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.