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

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert to find a minimum spanning tree. Start by crossing out row \(A\). Show which entries in the table are chosen and indicate the order in which the rows are deleted. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

3 Consider the following algorithm.
Step 1: Input a positive integer \(n\).
Step 2 : Draw a graph consisting of \(n\) vertices and no arcs.
Step 3 : Create a new vertex and join it directly to every vertex of order 0.
Step 4: Create a new vertex and join it directly to every vertex of odd order.
Step 5 : Stop.

1. Draw separate diagrams to show the result of applying this algorithm in the following cases.
   1. \(n = 1\)
   2. \(n = 2\)
   3. \(n = 3\)
   4. \(n = 4\)
   5. State how many arcs are in the graph that results when the algorithm is applied to a set of \(n\) vertices.

3 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. A simply connected graph is one that is both simple and connected.

1. A simply connected graph is drawn with 6 vertices and 9 arcs.
   1. What is the sum of the orders of the vertices?
   2. Explain why if the graph has two vertices of order 5 it cannot have any vertices of order 1.
   3. Explain why the graph cannot have three vertices of order 5 .
   4. Draw an example of a simply connected graph with 6 vertices and 9 arcs in which one of the vertices has order 5 and all the orders of the vertices are odd numbers.
   5. Draw an example of a simply connected graph with 6 vertices and 9 arcs that is also Eulerian.

2

1. Draw a graph with five vertices of orders 1, 2, 2, 3 and 4 .
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is.
3. Explain why a graph with five vertices of orders \(1,2,2,3\) and 4 cannot be a tree.

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

1. Explain why there is no simply connected graph with exactly five vertices each of which is connected to exactly three others.
2. A simply connected graph has five vertices \(A , B , C , D\) and \(E\), in which \(A\) has order \(4 , B\) has order 2, \(C\) has order 3, \(D\) has order 3 and \(E\) has order 2. Explain how you know that the graph is semi-Eulerian and write down a semi-Eulerian trail on this graph. A network is formed from the graph in part (ii) by weighting the arcs as given in the table below.

   	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)
   \(A\)	-	5	3	8	2
   \(B\)	5	-	6	-	-
   \(C\)	3	6	-	7	-
   \(D\)	8	-	7	-	9
   \(E\)	2	-	-	9	-

3. Apply Prim's algorithm to the network, showing all your working, starting at vertex \(A\). Draw the resulting tree and state its total weight. A sixth vertex, \(F\), is added to the network using arcs \(C F\) and \(D F\), each of which has weight 6 .
4. Use your answer to part (iii) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour. Explain why the nearest neighbour method fails if it is started from vertex \(F\).

6

1. Greatest number of arcs
   for a network with five vertices \(=\) \(\_\_\_\_\) for a network with \(n\) vertices \(=\) \(\_\_\_\_\)
2. (a) For a network with five vertices
   maximum number of passes \(=\) \(\_\_\_\_\) maximum number of comparisons
   in the first pass \(=\) \(\_\_\_\_\) in the second pass = \(\_\_\_\_\) in the third pass = \(\_\_\_\_\) maximum total number of comparisons = \(\_\_\_\_\) (b) For a network with \(n\) vertices
   maximum total number of comparisons = \(\_\_\_\_\)

3. M1 Vertices in tree	M2 Arcs in tree			M3 Vertices not in tree
   				A B C D E
   DE	D 2 \(E\)			\(A B C\)
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_109_220_1879_786}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_163_220_2005_786}
   				\multirow{3}{*}{}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_231_220_2174_786}

   \(\boldsymbol { M 4 }\)
   Sorted list

   \(|\)

   \(D\)	2	\(E\)
   \(A\)	3	\(E\)
   \(A\)	4	\(C\)
   \(C\)	5	\(D\)
   \(B\)	6	\(E\)
   \(B\)	7	\(C\)
   \(A\)	8	\(B\)
   \(C\)	9	\(E\)

4. \(\_\_\_\_\)

3

1. Explain why it is impossible to draw a graph with exactly four vertices of orders 1, 2, 3 and 3 . 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.
2. Explain why there is no simply connected graph with exactly four vertices of orders \(1,1,2\) and 4.
3. A connected graph has four vertices \(A , B , C\) and \(D\), in which \(A , B\) and \(C\) have order 2 and \(D\) has order 4. Explain how you know that the graph is Eulerian. Draw an example of such a graph and write down an Eulerian trail for your graph. A graph has three vertices, \(A , B\) and \(C\) of orders \(a , b\) and \(c\), respectively.
4. What restrictions on the values of \(a , b\) and \(c\) follow from the graph being
   1. simple,
   2. connected,
   3. semi-Eulerian?
      1. Describe carefully how to carry out the first pass through bubble sort when we are using it to sort a list of \(n\) numbers into increasing order. State which value is guaranteed to be in its correct final position after the first pass and hence explain how to carry out the second pass on a reduced list. Write down the stopping condition for bubble sort.
      2. Show the list of six values that results at the end of each pass when we use bubble sort to sort this list into increasing order. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$ You do not need to count the number of comparisons and the number of swaps that are used. Zack wants to cut lengths of wood from planks that are 20 feet long. The following lengths, in feet, are required. $$\begin{array} { l l l l l l } 3 & 10 & 8 & 2 & 6 & 11 \end{array}$$
      3. Use the first-fit method to find a way to cut the pieces.
      4. Use the first-fit decreasing method to find a way to cut the pieces. Give a reason why this might be a more useful cutting plan than that from part (iii).
      5. Find a more efficient way to cut the pieces. How many planks will Zack need with this cutting plan and how many cuts will he need to make? 5 An online shopping company selects some of its parcels to be checked before posting them. Each selected parcel must pass through three checks, which may be carried out in any order. One person must check the contents, another must check the postage and a third person must check the address. The parcels are classified according to the type of customer as 'new', 'occasional' or 'regular'. The table shows the time taken, in minutes, for each check on each type of parcel.
         1. Since \(a \leqslant 6\) it follows that \(6 - a \geqslant 0\), and similarly for \(b\) and \(c\). Let \(6 - a = x\) (so that \(a\) is replaced by \(6 - x ) , 8 - b = y\) and \(10 - c = z\) to show that the problem can be expressed as $$\begin{array} { l l } \text { Maximise } & 2 x - 4 y + 5 z , \\ \text { subject to } & 3 x + 2 y - z \leqslant 14 , \\ & 2 x - 4 z \leqslant 7 , \\ & - 4 x + y \leqslant 4 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$
         2. Represent the problem as an initial Simplex tableau. Perform two iterations of the Simplex algorithm, showing how each row was obtained. Hence write down the values of \(a , b\) and \(c\) after two iterations. Find the value of the objective for the original problem at this stage.
            [0pt] [10]

2 A tetromino is a two-dimensional shape made by joining four squares edge-to-edge. Joins are along complete edges.

1. Represent each of the tetrominoes below by a graph in which the nodes represent the squares and two nodes are joined by an arc if the squares share a common edge. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_76_268_1206_420} \captionsetup{labelformat=empty} \caption{(A)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_208_1201_836} \captionsetup{labelformat=empty} \caption{(B)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_144_1201_1165} \captionsetup{labelformat=empty} \caption{(C)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_145_209_1201_1439} \captionsetup{labelformat=empty} \caption{(D)}
   \end{figure}
2. Six simply connected graphs with four nodes are shown below. For each graph, either draw a tetromino that can be represented by the graph, as in part (i), or explain why this is not possible. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_126_1603_299} \captionsetup{labelformat=empty} \caption{(1)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_209_1603_529} \captionsetup{labelformat=empty} \caption{(2)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_125_1603_840} \captionsetup{labelformat=empty} \caption{(3)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_127_1603_1082} \captionsetup{labelformat=empty} \caption{(4)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1343} \captionsetup{labelformat=empty} \caption{(5)}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{012e87d3-d157-485c-a8bc-2c59c0862f87-2_122_122_1603_1603} \captionsetup{labelformat=empty} \caption{(6)}
   \end{figure} Two tetrominoes are regarded as being the same if one can be rotated or reflected to form the other. Derek claims that each tetromino corresponds to a unique tree with four nodes, and each tree with four nodes corresponds to a unique tetromino. Derek's claim is wrong.
3. From the diagrams above, find:
   1. a tetromino whose graph does not correspond to a tree;
   2. two different tetrominoes whose graphs correspond to the same tree. A pentomino is a two-dimensional shape made by joining five squares edge-to-edge. Joins are along complete edges. Two pentominoes are regarded as being the same if one can be rotated or reflected to form the other. There are twelve distinct pentominoes.
   3. When the pentominoes are represented by graphs, as in part (i), there are only four distinct graphs. Draw these four graphs.

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.

1. Draw a simple graph that connects four vertices using five arcs.
2. Explain why, in any graph, there must be an even number of odd vertices.
3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.

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.

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

1. Write down an example of a cycle on graph A .
2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
3. How many arcs would there be in a spanning tree for graph A ?
4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?

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

1. Explain why it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.
2. Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.
3. Explain why there is no simply connected graph with exactly four vertices of orders \(1,2,3\) and 4. State which of the properties 'simple' and 'connected' cannot be achieved.
4. A simply connected Eulerian graph has exactly five vertices.
   1. Explain why there cannot be exactly three vertices of order 4.
   2. By considering the vertex orders, explain why there are only four such graphs. Draw an example of each.

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

1. Explain why it is impossible to draw a graph with exactly five vertices of orders \(1,2,3,4\) and 5.
2. Explain why there is no simply connected graph with exactly five vertices of orders \(2,2,3,4\) and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.
3. Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.
4. Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree. In the graph below the vertices represent buildings and the arcs represent pathways between those buildings. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}
5. By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.

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

1. (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
   (b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
   (c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Revision classes}

   Student number	C1	C2	C3	C4	M1	M2	S1	S2	D1	D2
   1	✓	✓
   2				✓						✓
   3			✓	✓
   4			✓			✓
   5								✓	✓
   6		✓				✓
   7					✓			✓
   8	✓						✓
   9						✓				✓
   10					✓		✓

   \end{table}
2. (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
   (b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
   (c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).

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

1. (a) Draw a connected Eulerian graph that has exactly four vertices and five arcs but is not simple.
   (b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs. A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
2. (a) Explain how you know that the sum of the vertex orders must be 20 .
   (b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.
   (c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.

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

1. (a) Draw a simply connected graph that has exactly four vertices and exactly five arcs. Is your graph Eulerian, semi-Eulerian or neither? Explain how you know.
   (b) By considering the sum of the vertex orders, show that there is only one possible simply connected graph with exactly four vertices and exactly five arcs.
2. Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

• Two of the green faces are opposite one another.
• The other green face is opposite the yellow face.
• The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h] \end{figure} Fig. 1

1. Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
2. How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
   \end{figure} Fig. 3
3. Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled \(1,2,3\) or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure}
4. Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
   From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled \(1,2,3\) and 4 and four nodes each having order two.
5. Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
7. Using your answer to part (vi), show the two possible colourings of the back of the tower.

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.

1 The graph \(\mathrm { K } _ { 5 }\) has five nodes, \(A , B , C , D\) and \(E\), and there is an arc joining every node to every other node.

1. Draw the graph \(\mathrm { K } _ { 5 }\) and state how you know that it is Eulerian.
2. By listing the arcs involved, give an example of a path in \(\mathrm { K } _ { 5 }\). (Your path must include more than one arc.)
3. By listing the arcs involved, give an example of a cycle in \(\mathrm { K } _ { 5 }\).

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h] \end{figure}

1. Draw a tree to show all of the possibilities for the player's first three moves.
2. Show how a player can win in 3 turns.
3. List all squares which it is possible for a counter to occupy after 3 turns.
4. Show that a game can continue indefinitely.

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h] \end{figure}

1. Draw a tree to show all of the possibilities for the player's first three moves.
2. Show how a player can win in 3 turns.
3. List all squares which it is possible for a counter to occupy after 3 turns.
4. Show that a game can continue indefinitely.

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 graph shows routes that are available to an international lorry driver. The solid arcs represent motorways and the broken arcs represent ferry crossings. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-2_668_1131_587_466}

1. Give a route from Milan to Chania involving exactly two ferry crossings. How many such routes are there?
2. Give a route from Milan to Chania involving exactly three ferry crossings. How many such routes are there?
3. Give a route from Milan to Chania using as many ferry crossings as possible, without repeating any arc.
   [0pt]
4. Give a route leaving Piraeus and finishing elsewhere which uses every arc once and only once.[3]

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

2 The vertices of a graph are to be coloured using the following rules:

• all vertices are to be coloured
• no two vertices joined by an edge are to have the same colour.

The following graph has been coloured with four colours. \includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-2_357_883_1683_591} Kempe's rule allows for colours to be swapped. The rule is:

• choose two colours
• draw the subgraph consisting of the vertices coloured with these two colours, together with the edges that connect them
• in any connected part of this subgraph consisting of two or more vertices, the two colours can be swapped.
  1. Use Kempe's rule, choosing the colours blue and red.

Show that the graph can then be coloured with two colours.

Why does Kempe's rule not constitute an algorithm for colouring graphs?