7.02h Hamiltonian paths: and cycles

7

1. A simple connected graph \(X\) has eight vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
2. A simple connected graph \(Y\) has \(n\) vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
3. A simple graph \(Z\) has six vertices and each of the vertices has the same degree \(d\).
   1. State the possible values of \(d\).
   2. If \(Z\) is connected, state the possible values of \(d\).
   3. If \(Z\) is Eulerian, state the possible values of \(d\).

7

1. The diagram shows a graph with 16 vertices and 16 edges. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_365_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_365_1080} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_204_689_758} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_200_689_1082}
   1. On Figure 1 below, add the minimum number of edges to make a connected graph.
   2. On Figure 2 opposite, add the minimum number of edges to make the graph Hamiltonian.
   3. On Figure 3 opposite, add the minimum number of edges to make the graph Eulerian.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. 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\). \section*{Figure 1} \section*{Connected Graph} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_195_200_2014_758}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_197_200_2012_1082}
      \end{figure}
      \includegraphics[max width=\textwidth, alt={}]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_758}
      \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{(a)(i)} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-14_200_202_2334_1080}
      \end{figure} \section*{Figure 2} \section*{Hamiltonian Graph} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_218_536_511_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_213_212_836_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_215_214_836_1073}
      1. (iii) \section*{Eulerian Graph} \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_207_204_1356_758}
         \end{figure} \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_211_206_1354_1078}
         \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_206_209_1681_753} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-15_200_202_1681_1080}

6 The complete graph \(K _ { n } ( n > 1 )\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.

1. Draw the complete graph \(K _ { 4 }\).
2. 1. Find the total number of edges for the graph \(K _ { 8 }\).
   2. Give a reason why \(K _ { 8 }\) is not Eulerian.
3. For the graph \(K _ { n }\), state in terms of \(n\) :
   1. the total number of edges;
   2. the number of edges in a minimum spanning tree;
   3. the condition for \(K _ { n }\) to be Eulerian;
   4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.

2

1. A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.
2. Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer. A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is connected, directly or indirectly, to every other vertex.
3. Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.

4 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.

1. State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
2. (a) Explain how you know that Holly's graph is not simply connected.
   (b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
3. (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
   (b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
4. (a) What can you deduce about the vertex orders in Polly's graph?
   (b) Draw a graph that fits the description of Polly's graph.

3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey. \begin{figure}[h] \end{figure}

1. Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town. Give the start town and the end town.
2. Show that there is only one Hamilton cycle in the graph. Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.
3. A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B . Section B (48 marks)

1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths. \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}

1. Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths. Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2] Joanna, the householder, wants to walk along all of the paths.
2. Explain why she cannot do this without repeating at least one path.
3. Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated. Joanna has a new path constructed which links the pool directly to the top steps.
4. Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)

1 The directed bipartite graph represents links between chairlifts and ski runs in one part of a ski resort. Chairlifts are represented by capital letters, and ski runs are represented by numbers. For example, chairlift A takes skiers to the tops of ski runs 1 and 2, whereas ski run 2 takes skiers to the bottom of chairlift B . \includegraphics[max width=\textwidth, alt={}, center]{a27c868b-4fc4-4e82-b27f-d367b15b42c2-2_551_333_493_849}

1. The incomplete map in your answer book represents the three chairlifts and ski run 2 . Complete the map by drawing in the other 4 ski runs. Angus wants to ski all 5 ski runs, starting and finishing at the bottom of chairlift A .
2. Which chairlifts does Angus have to repeat, and why?
3. Which ski runs does Angus have to repeat, and why? The chairlifts and ski runs shown above form only part of the resort. In fact, chairlift C also takes skiers to the bottom of chairlift \(D\).
4. Why can this information not be represented in a bipartite graph?

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

1. Find a Hamiltonian cycle for the graph shown in Figure 1.
2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
   (5 marks)

4. \begin{figure}[h] \end{figure} Figure 3 shows the graph \(K _ { 4 }\).

1. State the features of the graph that identify it as \(K _ { 4 }\).
2. In \(K _ { 4 }\), the Hamiltonian cycles \(A B C D A , B C D A B , C D A B C\) and \(D A B C D\) are usually regarded as being the same cycle. Find the number of distinct Hamiltonian cycles in
   1. \(\quad K _ { 4 }\),
   2. \(K _ { 5 }\),
   3. \(K _ { 10 }\).
3. In a weighted network, 8 possible routes must be placed in ascending order according to their lengths. The routes have the following lengths in kilometres: $$\begin{array} { l l l l l l l l } 27 & 25 & 29 & 32 & 19 & 24 & 17 & 26 \end{array}$$ Use a quick sort to obtain the sorted list, giving the state of the list after each comparison and indicating the pivot elements used.

5. A clothes manufacturer has a trademark "VE" which it wants to embroider on all its garments. The stitching must be done continuously but stitching along the same line twice is allowed. Logo 1: \includegraphics[max width=\textwidth, alt={}, center]{acc09687-11a3-4392-af17-3d4d331d5ab4-06_524_1338_495_296} Logo 2: \begin{figure}[h] \end{figure} The weighted networks in Figure 4 represent two possible Logos.
The weights denote lengths in millimetres.

1. Calculate the shortest length of stitch required to embroider Logo 1 .
2. Calculate the shortest length of stitch required to embroider Logo 2.
3. Hence, determine the difference in the length of stitching required for the two Logos.

2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song. Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.

1. Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( \(1,2,3,4\) and 5 ) on the right hand side. The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
2. Explain why this would not be a satisfactory way to allocate the songs.
3. Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
4. Find a different allocation in which each of the five contestants is given a song that they chose. Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters. The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).

   \multirow{2}{*}{}	Character
   	Fire Chief	Gardener	Handyman	Juggler	King
   Adam	4	9	7	0	7
   Bex	6	8	3	8	0
   Chris	7	4	5	2	7
   Denny	6	6	2	7	1

   The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
5. Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
6. Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.

1

1. A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( \(F\) ), his mother Gwen ( \(G\) ), his wife Helen ( \(H\) ), his son Jack ( \(J\) ) and Mr King ( \(K\) ). The table shows who likes which rolls.

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Avocado and bacon	\(( A )\)	\(\checkmark\)		\(\checkmark\)
   Beef and horseradish	\(( B )\)		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
   Chicken and stuffing	\(( C )\)		\(\checkmark\)		\(\checkmark\)
   Duck and plum sauce	\(( D )\)			\(\checkmark\)		\(\checkmark\)
   Egg and tomato	\(( E )\)	\(\checkmark\)

   1. Draw a bipartite graph to represent this information. Put the fillings ( \(A , B , C , D\) and \(E\) ) on the left-hand side and the members of the family ( \(F , G , H , J\) and \(K\) ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
   2. Draw a second bipartite graph to show this incomplete matching.
   3. Construct the shortest possible alternating path from \(E\) to \(K\) and hence find a complete matching. State which roll each family member has with this complete matching.
   4. Find a different complete matching.
2. Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Family member}

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Lemon	\(L\)	8	8	8	8	1
   Mandarin	\(M\)	4	8	6	4	2
   Nectarine	\(N\)	9	9	9	7	1
   Orange	\(O\)	4	6	5	4	3
   Peach	\(P\)	6	9	7	5	0

   \end{table} The smaller entries in each column correspond to fruits that the family members liked most.
   Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
   Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?

1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.

1. Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, 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 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
4. Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.

1 The six cadets in Red Team have been told to guard a building through the night, starting at 2200 hours and finishing at 0800 hours the next day. Each will be on duty for either one hour or three hours and will then hand over to the next cadet. The table shows which duty each cadet has offered to take. \begin{table}[h] \end{table}

1. Draw a bipartite graph to represent this information. Amir suggests that he should take the 2200 duty, hand over to Becca at 0100 , she can hand over to Chris at 0200 , and Dan can take the 0400 duty. However, this leaves Emma and Finn to cover the 0300 and 0500 duties, and neither of them wants either of these.
2. Write down the shortest possible alternating path starting at the 0500 duty and hence write down an improved but still incomplete matching between the cadets and the duties.
3. Augment this second incomplete matching by writing down a shortest possible alternating path, this time starting from one of the cadets, to form a complete matching between the cadets and the duties. Write down which cadet should take which duty.

4 A connected graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}

1. Write down a path through exactly 7 of the vertices.
2. Write down a cycle through exactly 6 of the vertices.
3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
4. Prove that the graph is not Hamiltonian. 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, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
   STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
   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, output the word "bipartite".
   Otherwise the graph is not bipartite, output the words "not bipartite".
5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
6. Explain what Kuratowski's theorem tells you about the graph.
7. Show that the graph has thickness 2 .

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 .

1 This question is about the planar graph shown below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}

1. 1. Apply Kuratowski's theorem to verify that the graph is planar.
   2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
2. 1. Write down a Hamiltonian cycle for the graph.
   2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
3. 1. Draw the graph formed by using the contractions AB and CF .
   2. Use Ore's theorem to show that this contracted graph is Hamiltonian.

1. Figure 1 \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}

A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).

1. Complete this Hamiltonian cycle.
2. Hence use the planarity algorithm to determine if the graph is planar.

2. (a) Define the following terms

1. planar graph,
2. Hamiltonian cycle.
   (b) (i) Draw a graph of \(\mathrm { K } _ { 3,2 }\) in such a way as to show that it is planar.
3. Explain why the planarity algorithm cannot be used when drawing \(\mathrm { K } _ { 3,2 }\) as a planar graph.

1. \begin{figure}[h] \end{figure} A Hamiltonian cycle for the graph in Figure 1 begins \(\mathrm { C } , \mathrm { V } , \mathrm { E } , \mathrm { X } , \mathrm { A } , \mathrm { W } , \ldots\).

1. Complete the Hamiltonian cycle.
2. Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer.

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. (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. \begin{figure}[h] \end{figure}

1. Define what is meant by a planar graph.
2. Starting at A, find a Hamiltonian cycle for the graph in Figure 1. Arc AG is added to Figure 1 to create the graph shown in Figure 2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{37435cc9-1e38-4c55-bd72-e2a1ec415ba7-03_568_666_1226_701} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Taking ABCDEFGA as the Hamiltonian cycle,
3. use the planarity algorithm to determine whether the graph shown in Figure 2 is planar. You must make your working clear and justify your answer.

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?