7.02m Euler's formula: V + R = E + 2

1. \begin{figure}[h] \end{figure}

1. Find a Hamiltonian cycle for the graph shown in Figure 1.
2. Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
   (5 marks)

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

1. 1. Prove that the graphs are isomorphic.
   2. Verify that Euler's formula holds for graph G1.
2. Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
3. Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.

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.

4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

1. Figure 1 \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-2_473_682_348_614}

A Hamilton cycle for the graph in Fig. 1 begins \(A , X , D , V , \ldots\).

1. Complete this Hamiltonian cycle.
2. Hence use the planarity algorithm to determine if the graph is planar.

2. An electronics company makes a product that consists of components \(A , B , C , D , E\) and \(F\). The table shows which components must be connected together to make the product work. The components are all placed on a circuit board and connected by wires, which are not allowed to cross.

1. On the diagram in the answer book draw straight lines to show which components need to be connected.
   (1)
2. Starting with the Hamiltonian cycle \(A B C D E F A\), use the planarity algorithm to determine whether it is possible to build this product on a circuit board.
   (4)

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.

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.

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}

2 A connected planar graph has \(x\) vertices and \(2 x - 4\) edges.
Find the number of faces of the planar graph in terms of \(x\).
Circle your answer. \(x - 6\) \(x - 2\) \(6 - x\) \(2 - x\)

2 The graph \(D\) is shown in the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_115_150_1756_945} Which of the graphs below is a subdivision of \(D\) ?
Circle your answer. \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_218_154_2124_534} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_150_2129_808} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_154_2129_1082} \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_149_2129_1361}

4 The connected planar graph \(P\) has the adjacency matrix 4

1. Draw \(P\) 4
2. Using Euler's formula for connected planar graphs, show that \(P\) has exactly 5 faces. 4
3. Ore's theorem states that a simple graph with \(n\) vertices is Hamiltonian if, for every pair of vertices \(X\) and \(Y\) which are not adjacent, $$\text { degree of } X + \text { degree of } Y \geq n$$ where \(n \geq 3\) Using Ore's theorem, prove that the graph \(P\) is Hamiltonian.
   Fully justify your answer.

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}

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_1} Use the planarity algorithm to show that the graph in Fig. 1 is planar. [4]

A connected planar graph has \(v\) vertices, \(e\) edges and \(f\) faces. Which one of the formulae below is correct? Circle your answer. [1 mark] \(v + e + f = 2\) \quad\quad \(v - e + f = 2\) \quad\quad \(v - e - f = 2\) \quad\quad \(v + e - f = 2\)

Graph \(A\) is a connected planar graph with 12 vertices, 18 edges and \(n\) faces. Find the value of \(n\) Circle your answer. [1 mark] 4 8 28 32