7.02b Graph terminology: tree, simple, connected, simply connected

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

4. 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: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; } \\ & \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; } \\ & \text { Ms. Clough } ( C ) \text { - Monday; } \\ & \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; } \\ & \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ 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. Find another alternating path and hence obtain a complete matching.
   (3 marks)

8

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

6 A connected graph \(G\) has five vertices and has eight edges with lengths \(8,10,10,11,13,17\), 17 and 18.

1. Find the minimum length of a minimum spanning tree for \(G\).
2. Find the maximum length of a minimum spanning tree for \(G\).
3. Draw a sketch to show a possible graph \(G\) when the length of the minimum spanning tree is 53 .

4

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

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

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

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

7

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

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

1 The connected graph \(G\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{ecbeedf5-148e-40ad-b8a2-a7aa3db4a115-02_542_834_630_603} The graphs \(A\) and \(B\) are subgraphs of \(G\) Both \(A\) and \(B\) have four vertices. 1

1. The graph \(A\) is a tree with \(x\) edges.
   State the value of \(x\) Circle your answer. 3459 1
2. The graph \(B\) is simple-connected with \(y\) edges.
   Find the maximum possible value of \(y\) Circle your answer. 3459

1 The graph \(G\) has 8 vertices and 13 edges as shown in the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_494_392_482_806} Graph \(H\) is a simple-connected subgraph of graph \(G\) Which of the following diagrams could represent graph \(H\) ? Tick ( ✓ ) one box. \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_312_310_1354_351} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_321_310_1676_351} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_117_115_1448_822} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_312_310_2014_351} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_122_117_1777_822} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_314_314_2343_349} \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-03_120_115_2108_822}

8

1. The graph \(G\) has 2 vertices. The sum of the degrees of all the vertices of \(G\) is 6 Draw \(G\) 8
2. The planar graph \(P\) is Eulerian, with at least one vertex of degree \(x\), where \(x\) is a positive integer. Some of the properties of \(P\) are shown in the table below. Question number Additional page, if required. Write the question numbers in the left-hand margin. Question number Additional page, if required. Write the question numbers in the left-hand margin.

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.

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.
   \hfill [3]
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. \hfill [1]

The table below shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.

1. 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. \hfill [2]
2. 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. \hfill [3]
3. State the weight of the minimum spanning tree. \hfill [1]

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]

\includegraphics{figure_3}

1. Write down the name given to the type of graph drawn in Figure 3. (1)

A Hamiltonian cycle for the graph in Figure 3 begins A, 3, B, ....

1. Complete this Hamiltonian cycle. (2)
2. Starting with the Hamiltonian cycle found in (b), use the planarity algorithm to determine if the graph is planar. (3)

(Total 6 marks)

A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]

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]

Each of the following symbols consists of boundaries enclosing regions. \includegraphics{figure_1} The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics{figure_2} is \(\bullet \longrightarrow \bullet \longrightarrow \bullet\).

1. Produce the graph for the symbol \includegraphics{figure_3}. [1]
2. Give two symbols each having the graph \(\bullet \longrightarrow \bullet\). [2]
3. Produce the graph for the symbol \includegraphics{figure_4}. [2]
4. Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
5. Give the name of a connected graph with \(n\) nodes and \(n - 1\) arcs. [1]

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