Euler's formula application

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}

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

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

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

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]