7.02g Eulerian graphs: vertex degrees and traversability

6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.

1. A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
2. Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
3. Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
4. A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.

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

2 The graph \(G\) has 5 vertices and 6 edges, as shown below. \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-03_547_547_360_749} Which of the following statements describes the properties of \(G\) ?
Tick ( \(\checkmark\) ) one box. \(G\) is Eulerian and Hamiltonian. □ \(G\) is Eulerian but not Hamiltonian. □ \(G\) is semi-Eulerian and Hamiltonian. □ \(G\) is semi-Eulerian but not Hamiltonian. □

5 The planar graph \(P\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-08_410_406_360_817} 5

1. Determine the number of faces of \(P\).
   5
2. Akwasi claims that \(P\) is semi-Eulerian as it is connected and it has exactly two vertices with even degree. Comment on the validity of Akwasi's claim. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-09_2488_1716_219_153}

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.

3. \begin{figure}[h] \end{figure} [The weight of the network is \(5 x + 246\) ]

1. Explain why it is not possible to draw a graph with an odd number of vertices of odd valency. Figure 2 represents a network of 14 roads in a town. The expression on each arc gives the time, in minutes, to travel along the corresponding road. Prim's algorithm, starting at A, is applied to the network. The order in which the arcs are selected is \(\mathrm { AD } , \mathrm { DH } , \mathrm { DG } , \mathrm { FG } , \mathrm { EF } , \mathrm { CG } , \mathrm { BD }\). It is given that the order in which the arcs are selected is unique.
2. Using this information, find the smallest possible range of values for \(x\), showing your working clearly. A route that minimises the total time taken to traverse each road at least once is required. The route must start and finish at the same vertex. Given that the time taken to traverse this route is 318 minutes,
3. use an appropriate algorithm to determine the value of \(x\), showing your working clearly.

3 The diagram shows a simplified map of the main streets in a small town. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246} Some of the junctions have traffic lights, these junctions are labelled A to F .
There are no traffic lights at junctions X and Y .
The numbers show distances, in km, between junctions. Alex needs to check that the traffic lights at junctions A to F are working correctly.

1. Find a route from A to E that has length 2.8 km . Alex has started to construct a table of shortest distances between junctions A to F. \includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246} For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
2. Complete the copy of the table in the Printed Answer Booklet.
3. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
   Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
4. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c).

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.

This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed (A) -- Monday and Wednesday; Miss Brown (B) -- Monday, Wednesday and Friday; Ms. Clough (C) -- Monday; Mr. Dingle (D) -- Tuesday, Wednesday and Thursday; Mrs. Evans (E) -- Wednesday and Thursday. The manager initially suggests that A might work on Monday, B on Wednesday and D on Thursday.

1. Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion. [2 marks]
2. Obtain an alternating path, starting at C, and use this to improve the initial matching. [3 marks]
3. Find another alternating path and hence obtain a complete matching. [3 marks]

Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs 1, 2, 3, 4 or 5. The table shows each member's preferences for the jobs. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.

1. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs. [2]
2. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path. [3]
3. Find a second alternating path from the initial allocation. [1]

Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres. Norris starts from the newsagents located at vertex \(A\), and he must walk along all the streets at least once before returning to the newsagents. \includegraphics{figure_5} The total length of the streets is 1215 metres.

1. Give a reason why it is not possible to start at \(A\), walk along each street once only, and return to \(A\). [1]
2. Find the length of an optimal Chinese postman route around the estate, starting and finishing at \(A\). [5]
3. For an optimal Chinese postman route, state:
   1. the number of times that the vertex \(F\) would occur; [1]
   2. the number of times that the vertex \(H\) would occur. [1]

A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4. \includegraphics{figure_1} A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.

1. Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [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. What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
2. What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]

\includegraphics{figure_2}

1. Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3. [1]

A simple graph is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined 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. 1. Draw a graph with five vertices of orders 1, 1, 2, 2 and 4 that is neither simple nor connected. [2]
   2. Explain why your graph from part (a) is not semi-Eulerian. [1]
   3. Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. [1]

Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.

1. 1. Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour. [2]
   2. Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour. [2]

An adjacency matrix for the simple graph \(G\) is shown below. \includegraphics{figure_5}

1. Using the adjacency matrix, explain why \(G\) is not a complete graph. [2 marks]
2. State, with a reason, whether \(G\) is Eulerian, semi-Eulerian or neither. [2 marks]
3. Draw a graph that is the complement of \(G\) [3 marks]

A jeweller is making pendants. Each pendant is made by bending a single, continuous strand of wire. Each pendant has the same design as shown below. \includegraphics{figure_7} The lengths on the diagram are in millimetres. The sum of these lengths is 240 mm As the jeweller does not cut the wire, some sections require a double length of wire.

1. The jeweller makes a pendant by starting and finishing at \(B\) Find the minimum length of the strand of wire that the jeweller needs to make the pendant. Fully justify your answer. [4 marks]
2. The jeweller makes another pendant of the same design. Find the minimum possible length for the strand of wire that the jeweller would need. [2 marks]
3. By considering the differences between the pendants in part (a) and part (b), state one reason why the jeweller may prefer the pendant in part (a). [1 mark]

Which one of the graphs shown below is semi-Eulerian? Tick (\(\checkmark\)) one box. [1 mark] \includegraphics{figure_3}

A council wants to convert all of the street lighting in a village to use LED lighting. The network below shows each street in the village. Each node represents a junction and the weight of each arc represents the length, in metres, of the street. The street lights are only positioned on one side of each street in the village. \includegraphics{figure_6} The total length of all of the streets in the village is 2250 metres. In order to determine the total number of street lights in the village, a council worker is required to walk along every street in the village at least once, starting and finishing at the same junction. The shortest possible distance the council worker can walk in order to determine the total number of street lights in the village is \(x\) metres.

1. Find the value of \(x\) Fully justify your answer. [4 marks]
2. A new council regulation requires that the mean distance along a street between adjacent LED street lights in a village be less than 25 metres. The council worker counted 91 different street lights on their journey around the village. Determine whether or not the village will meet the new council regulation. [2 marks]

The simple-connected graph \(G\) has the adjacency matrix $$\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 1 & 1 \\ B & 1 & 0 & 1 & 0 \\ C & 1 & 1 & 0 & 1 \\ D & 1 & 0 & 1 & 0 \\ \end{array}$$ Which one of the following statements about \(G\) is true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is a tree \(\square\) \(G\) is complete \(\square\) \(G\) is Eulerian \(\square\) \(G\) is planar \(\square\)

A planar graph \(G\) is described by the adjacency matrix below. $$\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$

1. Draw the graph \(G\). [1]
2. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]
3. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(AB\). Deduce how many Hamiltonian cycles graph \(G\) has. [4]

A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1. STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2. STEP 4: Go back to STEP 2.

1. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. [2]

By removing just one edge from graph \(G\) it is possible to make a bipartite graph.

1. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]

Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

1. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]