7.02j Isomorphism: of graphs, degree sequences

1 The numbers on opposite faces of the die shown (a standard die) add up to 7. The adjacency graph for the die is a graph which has vertices representing faces. In the adjacency graph two vertices are joined with an arc if they share an edge of the die. For example, vertices 2 and 6 are joined by an arc because they share an edge of the die. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_246_213_488_1608}

1. List the pairs of numbers which are opposite each other.
2. Draw the adjacency graph.
3. Identify and sketch a solid which has the following adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_287_307_1027_879}

3 The adjacency graph of a cube \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
   (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

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.

4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down a semi-Eulerian route for graph 1 .
2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
3. By referring to specific vertices, explain how you know that these graphs are not simple.
4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.

5 There are three non-isomorphic trees on five vertices.

1. Draw an example of each of these trees.
2. State three properties that must be satisfied by the vertex orders of a tree on six vertices.
3. List the five different sets of possible vertex orders for trees on six vertices.
4. Draw an example of each type listed in part (iii).

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 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6

1. Explain why it is not possible to find a complete matching. Figure 2 shows an initial matching. Starting from this initial matching,
2. find the two alternating paths that start at C .
3. List the two improved matchings generated by using the two alternating paths found in (b). After training, task 5 is added to Bernard's possible allocation.
   Starting from either of the two improved matchings found in (c),
4. use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used and state your improved matching.
2. Explain why it is not possible to find a complete matching. Now, exactly one worker may be trained so that a complete matching becomes possible.
   Either worker A can be trained to do task 1 or worker E can be trained to do task 4.
3. Decide which worker, A or E , should be trained. Give a reason for your answer. You may now assume that the worker you identified in (c) has been trained.
4. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used and state your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.

1. Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 1 is added to worker A's possible allocations.
3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, \(1,2,3\), 4, 5 and 6 Figure 2 shows an initial matching.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.

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.

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 . \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down a semi-Eulerian route for graph 1.
2. Explain how the vertex orders show that graph 2 is also semi-Eulerian.
3. By referring to specific vertices, explain how you know that these graphs are not simple.
4. By referring to specific vertices, explain how you know that these graphs are not isomorphic.

The graph below connects nine vertices A, B, \(\ldots\), H, I. \includegraphics{figure_2}

1. 1. Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
   2. Explain what you can deduce from the result in part (a). [1]
2. Use Kuratowski's theorem to prove that the graph is non-planar. [3]
3. Prove that there is no subgraph of the graph that is isomorphic to \(K_4\), without using subdivision or contraction. [6]