7.02a Graphs: vertices (nodes) and arcs (edges)

1 A TV soap opera has five main characters, Alice ( \(A\) ), Bob ( \(B\) ), Charlie ( \(C\) ), Dylan ( \(D\) ) and Etty ( \(E\) ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( \(F\) ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( \(G\) ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( \(J\) ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

1. Draw a bipartite graph to show which main characters ( \(A , B , C , D , E\) ) are in which of the next five episodes \(( F , G , H , I , J )\). The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
2. Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
3. From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
4. By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h] \end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.

1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).

• Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
• Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
• Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
• Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
  1. Draw a bipartite graph to show which suspects could come to tea on which day.

Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.

Draw a second bipartite graph to show this incomplete matching.

Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.

Who does Agatha accuse of being guilty?

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

• Arthur wants to use lavender, orange or tangerine.
• Bridget wants to use lavender, mauve or pink.
• Carlos wants to use pink or scarlet.
• Davinder wants to use mauve or pink.
• Eric wants to use lavender or orange.
• Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

1. Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
3. Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

1 Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of the four children. The results are shown in the Venn diagram below. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-2_387_618_589_246}

1. Construct a complete graph \(\mathrm { K } _ { 4 }\), with vertices representing the four children and arcs weighted to show the number of parties each pair of children went to.
2. State a piece of information about the number of parties the children went to that is shown in the Venn diagram but is not shown in the graph. A fifth child, E, also went to some of the 23 parties shown in the Venn diagram.
   Every party that E went to was also attended by at least one of \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .

2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. The table below shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .

   	A	B	C	D	E	F	G
   A	-	17	-	19	30	-	-
   B	17	-	21	23	-	-	-
   C	-	21	-	27	29	31	22
   D	19	23	27	-	-	40	-
   E	30	-	29	-	-	33	25
   F	-	-	31	40	33	-	39
   G	-	-	22	-	25	39	-

3. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
4. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
5. State the weight of the minimum spanning tree.

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.

6. This question is to be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.

1. Explain why it is not possible to achieve a flow of 30 through the network from \(S\) to \(T\).
2. State the maximum flow along
   1. \(S A B T\)
   2. SCET.
3. Show these flows on Diagram 1 of the answer sheet.
4. Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from \(S\) to \(T\). Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
5. Indicate a maximum flow on Diagram 3.
6. Prove that your flow is maximal.

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. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.
   (4)
2. Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\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 the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
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 used and your complete matching.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, \(1,2,3,4,5\) and 6.

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.
   (6)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five employees, Ali (A), Campbell (C), Hugo (H), Janelle (J) and Polly (P), to five tasks 1, 2, 3, 4 and 5.

1. Explain why it is not possible to find a complete matching. It is decided that one of the employees should be trained so that a complete matching becomes possible. There are only enough funds for one employee to be trained. Two employees volunteer to undergo training. Janelle can be trained to do task 1 or Hugo can be trained to do task 5.
2. Decide which employee, Janelle or Hugo, should undergo training. Give a reason for your answer. You may now assume that the employee you identified in (b) has successfully undergone training. Figure 2 shows an initial matching.
3. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state the complete matching.

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 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\).

8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.

1. A simple graph has five vertices and their degrees are $$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
   1. Show that \(x\) must be odd.
   2. Find the value of \(x\) and draw a graph with vertices having the given degrees.
2. A simple graph has 10 vertices.
   1. State the minimum possible degree and maximum possible degree of a vertex.
   2. Show that the degrees of the vertices cannot all be different.
      □
      □

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)

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).

7

1. 1. Complete Figure 4 to identify the feasible region for the problem. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5a826f8b-4751-4589-ad0a-109fc5c821f2-12_922_940_849_552}
      \end{figure} 7
      1. (ii) Determine the maximum value of \(5 x + 4 y\) subject to the constraints.
         7
   2. The simple-connected graph \(G\) has seven vertices. The vertices of \(G\) have degree \(1,2,3 , v , w , x\) and \(y\) 7
   3. 1. Explain why \(x \geq 1\) and \(y \geq 1\) 7
      2. Explain why \(x \leq 6\) and \(y \leq 6\) 7
      3. Explain why \(x + y \leq 11\) 7
      4. State an additional constraint that applies to the values of \(x\) and \(y\) in this context.
         7
      5. The graph \(G\) also has eight edges. The inequalities used in part (a)(i) apply to the graph \(G\).
      7
   4. 1. Given that \(v + w = 4\), find all the feasible values of \(x\) and \(y\).
         7
   5. (ii) It is also given that the graph \(G\) is semi-Eulerian. On Figure 5, draw \(G\). Figure 5

1 A graph has 5 vertices and 6 edges.
Find the sum of the degrees of the vertices. Circle your answer. 10111215

8 The graph \(G\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-12_301_688_351_676} 8

1. 1. State, with a reason, whether or not \(G\) is simple. 8
      1. (ii) A student states that \(G\) is Eulerian.
         Explain why the student is correct. 8
   2. The graph \(H\) has 8 vertices with degrees 2, 2, 4, 4, 4, 4, 4 and 4 Comment on whether \(H\) is isomorphic to \(G\) 8
   3. The formula \(v - e + f = 2\), where \(v =\) number of vertices \(e =\) number of edges \(f =\) number of faces
      can be used with graphs which satisfy certain conditions. Prove that \(G\) does not satisfy the conditions for the above formula to apply.