7.02g Eulerian graphs: vertex degrees and traversability

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. 1. Explain why graph G cannot be a complete graph.
   2. Determine the number of arcs in graph G, explaining your reasoning.
   3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{To}

      	A	B	C	D
      A	0	1	0	1
      B	0	0	2	0
      C	2	1	0	1
      D	0	1	1	0

      \end{table}
2. 1. Write down a feature of the adjacency matrix that shows that H has no loops.
   2. Find the number of \(\operatorname { arcs }\) in H .
   3. Draw a possible digraph H .
   4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

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.

2 A graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c4755464-aa15-4720-8f33-5eb7169f4a20-2_522_810_1637_246}

1. Write down a cycle through all six vertices.
2. Write down a continuous route that uses every arc exactly once.
3. Use Kuratowski's theorem to show that the graph is not planar.
4. Show that the graph has thickness 2 .

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

1. 1. Determine the minimum possible vertex degree.
   2. Determine the maximum possible vertex degree.
2. Write down the two possible degree sequences (ordered lists of vertex degrees). The adjacency matrix for a digraph H is given below.

   \multirow{7}{*}{From}	\multirow{2}{*}{}	To
   		J	K	L	M	N
   	J	0	1	1	0	0
   	K	1	0	1	0	0
   	L	1	0	0	0	1
   	M	0	0	2	1	1
   	N	0	1	0	1	0

3. Write down the indegree and the outdegree of each vertex of H .
4. 1. Use the indegrees and outdegrees to determine whether graph H is Eulerian.
   2. Use the adjacency matrix to determine whether graph H is simply connected.

2.

1. 1. Define the term complete matching.
   2. Explain the difference between a complete matching and a maximal matching.
      (3) \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_732_563_434_376} \captionsetup{labelformat=empty} \caption{Figure 1}
      \end{figure} \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_739_563_429_1117} \captionsetup{labelformat=empty} \caption{Figure 2}
      \end{figure} Figure 1 shows the possible allocations of dancing partners for the Truly Come Ballroom dancing competition. Six women, Annie (A), Bella (B), Chloe (C), Danika (D), Ella (E) and Faith (F), are to be paired with six men, Kieran (K), Lucas (L), Michael (M), Nasir (N), Oliver (O) and Paul (P). Figure 2 shows an initial matching.
2. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and list your improved matching.
   (3) After dance practice, it is decided that Bella could also be paired with Kieran, and Danika could also be paired with Nasir.
3. Starting with your improved matching from part (b), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and list your final matching.
   

4. (a) Define the term 'alternating path'. \begin{figure}[h] \end{figure} Figure 4 shows the possible allocations of five people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , to five tasks, \(1,2,3,4\) and 5 An initial matching has three people allocated to three of the tasks.
Starting from this initial matching, one possible alternating path that starts at E is $$E - 2 = B - 3 = A - 4 = D - 1$$ (b) Use this information to

1. deduce this initial matching,
2. list the improved matching generated by the given alternating path.
   (c) Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.

2. (a) Define the terms

1. alternating path,
2. complete matching.
   (4) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098} \captionsetup{labelformat=empty} \caption{Figure 2}
   \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.
   (b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.
   (3)
   (c) Explain why it is not possible to find a complete matching.
   (1) Worker C has task 1 added to his possible allocations.
   (d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 2 shows the possible allocations of six workers, Charlie (C), George (G), Jack (J), Nurry (N), Olivia (O) and Rachel (R), to six tasks, \(1,2,3,4,5\) and 6. Figure 3 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should give the alternating path you use and list your improved matching.
2. Explain why it is not possible to find a complete matching. After training, Charlie adds task 5 to his possible allocations.
3. Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. Give the alternating path you use and list your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Five members of staff \(1,2,3,4\) and 5 are to be matched to five jobs \(A , B , C , D\) and \(E\). A bipartite graph showing the possible matchings is given in Fig. 1 and an initial matching \(M\) is given in Fig. 2. There are several distinct alternating paths that can be generated from \(M\). Two such paths are $$2 - B = 4 - E$$ and $$2 - A = 3 - D = 5 - E$$

1. Use each of these two alternating paths, in turn, to write down the complete matchings they generate. Using the maximum matching algorithm and the initial matching \(M\),
2. find two further distinct alternating paths, making your reasoning clear. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{652477eb-87dc-4a5a-8514-c9be39986142-4_577_1476_367_333}
   \end{figure} Figure 3 shows the network of paths in a country park. The number on each path gives its length in km . The vertices \(A\) and \(I\) represent the two gates in the park and the vertices \(B , C , D , E , F , G\) and \(H\) represent places of interest.

2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

1. Given that a simply connected graph has exactly four vertices,
   1. write down the minimum number of arcs it can have,
   2. write down the maximum number of arcs it can have.
2. 1. Draw a simply connected graph that has exactly four vertices and exactly five arcs.
   2. State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
3. By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 120]

1. Explain what is meant by the term "path".
2. State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither. Figure 2 represents a network of cycle tracks between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc represents the length, in km , of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
3. Use Dijkstra's algorithm to find the shortest path that Samira can take. An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G . Daisy plans to cycle along every track in the new network, starting and finishing at H .
   Given that the addition of either track CD or track EG will not affect the final values obtained in (c),
4. use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must

5. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 3\) ] Figure 4 shows a graph G that contains 8 arcs and 6 vertices.

1. State the minimum number of arcs that would need to be added to make G into an Eulerian graph.
2. Explain whether or not the route \(\mathrm { A } - \mathrm { C } - \mathrm { F } - \mathrm { E } - \mathrm { C } - \mathrm { D } - \mathrm { B }\) is an example of a path on G. Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road. You are given that \(x > 1.6\) A route is required that
   The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes. Given that the inspection route contains two roads that need to be traversed twice,
3. determine the range of possible values of \(x\), making your reasoning clear.

4.

1. Explain why it is not possible to draw a graph with exactly 5 nodes with orders \(1,3,4,4\) and 5 A connected graph has exactly 5 nodes and contains 18 arcs. The orders of the 5 nodes are \(2 ^ { 2 x } - 1,2 ^ { x } , x + 1,2 ^ { x + 1 } - 3\) and \(11 - x\).
2. 1. Calculate X .
   2. State whether the graph is Eulerian, semi-Eulerian or neither. You must justify your answer.
3. Draw a graph which satisfies all of the following conditions:

6. \begin{figure}[h] \end{figure} [The total weight of the network is \(320 + x + y\) ]

1. State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 < x < 26\) and the weight on arc DG is \(y\) where \(0 < y < 10\) An inspection route of minimum length that traverses each arc at least once is found.
   The inspection route starts and finishes at A and has a length of 409
   It is also given that the length of the shortest route from F to G via A is 140
2. Using appropriate algorithms, find the value of \(x\) and the value of \(y\).

1. \begin{figure}[h] \end{figure} Figure 1 shows the graph G.

1. State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer.
2. Write down an example of a Hamiltonian cycle on G.
3. State whether or not G is planar, justifying your answer.
4. State the number of arcs that would need to be added to G to make the graph \(\mathrm { K } _ { 5 }\) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6ccce35f-4e62-4b6b-acf6-f9b3e18d4b52-03_467_716_178_671} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the five villages.
5. For the network represented in Figure 2, complete the initial time matrix in the answer book. The time matrix after four iterations of Floyd's algorithm is shown in Table 1. \begin{table}[h]

   	A	B	C	D	E
   A	-	10	13	15	5
   B	10	-	3	5	4
   C	13	3	-	2	7
   D	15	5	2	-	7
   E	5	4	7	7	-

   \captionsetup{labelformat=empty} \caption{Table 1}
   \end{table}
6. Perform the final iteration of Floyd's algorithm that follows from Table 1, showing the time matrix for this iteration.

4.

1. 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.
2. Explain how you know that T cannot be Eulerian.
3. 1. Determine the value of \(x\)
   2. 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
4. 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 .
   

1 The design for the lines on a playing area for a game is shown below. The letters are not part of the design. \includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-2_350_855_388_605} Priya paints the lines by pushing a machine. When she is pushing the machine she is about a metre behind the point being painted. She must not duplicate any line by painting it twice.

• To relocate the machine, it must be stopped and then started again to continue painting the lines.
• When the machine is being relocated it must still be pushed along the lines of the design, and not 'cut across' on a diagonal for example.
• The machine can be turned through \(90 ^ { \circ }\) without having to be stopped.
  1. What is the minimum number of times that the machine will need to be started to paint the design?

The design is horizontally and vertically symmetric. $$\mathrm { AB } = 6 \text { metres, } \mathrm { AE } = 26 \text { metres, } \mathrm { AF } = 1.5 \text { metres and } \mathrm { AS } = 9 \text { metres. }$$

(a) Find the minimum distance that Priya needs to walk to paint the design. You should show enough working to make your reasoning clear but you do not need to use an algorithmic method.
(b) Why, in practice, will the distance be greater than this?
(c) What additional information would you need to calculate a more accurate shortest distance?

7 A simply connected graph has 6 vertices and 10 arcs.

1. What is the maximum vertex degree? You are now given that the graph is also Eulerian.
2. Explaining your reasoning carefully, show that exactly two of the vertices have degree 2 .
3. Prove that the vertices of degree 2 cannot be adjacent to one another.
4. Use Kuratowski's theorem to show that the graph is planar.
5. Show that it is possible to make a non-planar graph by the addition of one more arc. A digraph is created from a simply connected graph with 6 vertices and \(10 \operatorname { arcs }\) by making each arc into a single directed arc.
6. What can be deduced about the indegrees and outdegrees?
7. If a Hamiltonian cycle exists on the digraph, what can be deduced about the indegrees and outdegrees? \section*{OCR} \section*{Oxford Cambridge and RSA}

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.

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-007_1539_1162_495_424} Stella leaves the bus station at \(A\). She decides to walk along all of the roads at least once before returning to \(A\).

1. Explain why it is not possible to start from \(A\), travel along each road only once and return to \(A\).
2. Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at \(A\).
3. At each of the 9 places \(B , C , \ldots , J\), there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_1539_1162_495_424} Stella leaves the bus station at \(A\). She decides to walk along all of the roads at least once before returning to \(A\).

1. Explain why it is not possible to start from \(A\), travel along each road only once and return to \(A\).
2. Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at \(A\).
3. At each of the 9 places \(B , C , \ldots , J\), there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.

8

1. The diagram shows a graph \(\mathbf { G }\) with 9 vertices and 9 edges. \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105} \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
   1. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make a connected graph. Draw an example of such a graph.
   2. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Hamiltonian. Draw an example of such a graph.
   3. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Eulerian. Draw an example of such a graph.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\).

4

1. In the complete graph \(\mathrm { K } _ { 7 }\), every one of the 7 vertices is connected to each of the other 6 vertices by a single edge. Find or write down:
   1. the number of edges in the graph;
   2. the number of edges in a minimum spanning tree;
   3. the number of edges in a Hamiltonian cycle.
2. 1. Explain why the graph \(\mathrm { K } _ { 7 }\) is Eulerian.
   2. Write down the condition for \(\mathrm { K } _ { n }\) to be Eulerian.
3. A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.

7 A connected graph \(\mathbf { G }\) has \(m\) vertices and \(n\) edges.

1. 1. Write down the number of edges in a minimum spanning tree of \(\mathbf { G }\).
   2. Hence write down an inequality relating \(m\) and \(n\).
2. The graph \(\mathbf { G }\) contains a Hamiltonian cycle. Write down the number of edges in this cycle.
3. In the case where \(\mathbf { G }\) is Eulerian, draw a graph of \(\mathbf { G }\) for which \(m = 6\) and \(n = 12\).

7

1. A simple connected graph has 4 edges and \(m\) vertices. State the possible values of \(m\).
2. A simple connected graph has \(n\) edges and 4 vertices. State the possible values of \(n\).
3. A simple connected graph, \(G\), has 5 vertices and is Eulerian but not Hamiltonian. Draw a possible graph \(G\).
   [0pt] [2 marks]