7.02l Planar graphs: planarity, subdivision, contraction

3 Traffic flows in and out of a junction of three roads as shown in the diagram. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_296_337_333_863} Assuming that no traffic leaves the junction by the same road as it entered, then the digraph shows traffic flows across the junction. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_362_511_852_776}

1. Redraw the digraph to show that it is planar.
2. Draw a digraph to show the traffic flow across the junction of 4 roads, assuming that no traffic leaves the junction by the same road as it entered. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_366_366_1512_854}
   (Note that the resulting digraph is also planar, but you are not required to show this.)
3. The digraphs showing flows across the junctions omit an important aspect in their modelling of the road junctions. What is it that they omit?

1. (a) Make plane drawings of each of the graphs shown in Figure 1.

Graph 1 \begin{figure}[h] \end{figure} (b) State the name given to Graph 1 and write down the features that identify it.
(c) State, with a reason, whether it is possible to add further arcs to Graph 2 such that it remains a simple connected graph. No further vertices may be added.
(1 mark)

2 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. List the vertex degrees for each graph.
2. Prove that the graphs are non-isomorphic. The two graphs are joined together by adding an arc connecting J and T .
3. 1. Explain how you know that the resulting graph is not Eulerian.
   2. Describe how the graph can be made Eulerian by adding one more arc. The vertices of the graph \(K _ { 3 }\) are connected to the vertices of the graph \(K _ { 4 }\) to form the graph \(K _ { 7 }\).
4. Explain why 12 arcs are needed connecting \(K _ { 3 }\) to \(K _ { 4 }\).

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.

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 Which of the following graphs is not planar? Circle your answer.
[0pt] [1 mark] \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_186_301_1000_520} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_218_224_986_884} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_236_982_1201} \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-02_241_241_982_1521}

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.

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.

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.

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

1. Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
2. Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
3. Repeat parts (i) and (ii) for the following map. \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

4 The connected planar graph \(P\) is Eulerian and has at least one vertex of degree \(x\). Some of the properties of \(P\) are shown in the table below. Deduce the value of \(x\).
Fully justify your answer. \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-07_2488_1716_219_153}

5

1. A connected planar graph has 9 vertices, 20 edges and \(f\) faces. Use Euler's formula for connected planar graphs to find \(f\) 5
2. The graph \(J\), shown in Figure 1, has 9 vertices and 20 edges. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{ecbeedf5-148e-40ad-b8a2-a7aa3db4a115-09_778_760_440_641}
   \end{figure} By redrawing the graph \(J\) using Figure 2, show that \(J\) is planar. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2}

   \(A\)	\(B\)	\(C\)
   \(\bullet\)	\(\bullet\)	\(\bullet\)
   \(D \bullet\)	\(E \bullet\)	\(\bullet F\)
   \(\bullet\)	\(\stackrel { \theta } { H }\)	\(\bullet\)

   \end{table}

6

1. A connected planar graph has \(( x + 1 ) ^ { 2 }\) vertices, \(( 25 + 2 x - 2 y )\) edges and \(( y - 1 ) ^ { 2 }\) faces, where \(x > 0\) and \(y > 0\) Find the possible values for the number of vertices, edges and faces for the graph.
   [0pt] [6 marks]
   LL
   6
2. Explain why \(K _ { 6 }\), the complete graph with 6 vertices, is not planar. Fully justify your answer.

1 The simple-connected graph \(G\) is shown below. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-02_271_515_632_762} The graph \(G\) has \(n\) faces. State the value of \(n\) Circle your answer. 2345

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.

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

The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2]
2. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use. [3]
3. Explain why it is not possible to find a complete matching. [2]

\includegraphics{figure_1}

1. Starting from \(A\); write down a Hamiltonian cycle for the graph in Figure 1. [2]
2. Use the planarity algorithm to show that the graph in Figure 1 is planar. [3]

Arcs \(AF\) and \(EF\) are now added to the graph.

1. Explain why the new graph is not planar. [2]

(Total 7 marks)

\includegraphics{figure_3} \includegraphics{figure_4} A film critic, Verity, must see five films A, B, C, D and E over two days. The films are being shown at five special critics' preview times: \begin{align} 1 &\text{ (Monday 4 pm),}
2 &\text{ (Monday 7 pm),}
3 &\text{ (Tuesday 1 pm),}
4 &\text{ (Tuesday 4 pm),}
5 &\text{ (Tuesday 7 pm).} \end{align} The bipartite graph in Figure 3 shows the times at which each film is showing. Initially Verity intends to see \begin{align} &\text{Film A on Monday at 4 pm,}
&\text{Film B on Tuesday at 4 pm,}
&\text{Film C on Tuesday at 1 pm,}
&\text{Film D on Monday at 7 pm.} \end{align} This initial matching is shown in Figure 4. Using the maximum matching algorithm and the given initial matching,

1. find two distinct alternating paths and complete the matchings they give. [6]

Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.

1. Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. [2]

(Total 8 marks)

Explain what is meant by a planar graph. (Total 2 marks)

\includegraphics{figure_1} \includegraphics{figure_2} Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5. For safety reasons, task 1 must be done by two people working together. A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2. The maximum matching algorithm will be used to obtain a complete matching.

1. Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm. [2]
2. Find an alternating path and the complete matching it gives. [3]

Hannah is now unable to do task 5 due to health reasons.

1. Explain why a complete matching is no longer possible. [2]

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