Kuratowski's theoremAQA A-Level Further Maths: Subtopic test

1. 1
   The complete graph $K_5$ has five vertices, each joined to every other vertex.

   (a)

   How many edges does $K_5$ have?

   [1 mark]

   • A$5$
   • B$10$
   • C$20$
   • D$25$

   (b)

   The graph $K$ is formed from $K_5$ by deleting one edge. Which statement about $K$ is correct?

   [1 mark]

   • ANon-planar, because it still has five vertices each of degree at least 3
   • BNon-planar, because every graph with 5 vertices and 9 edges is non-planar
   • CPlanar, because it contains no subdivision of $K_5$ or of $K_{3,3}$
   • DIt cannot be decided without trying to draw it

   (c)

   A new vertex $w$ is placed in the middle of one edge of $K_5$, replacing that edge by two edges, to give a graph $H$. State the number of edges of $H$ and explain whether $H$ is planar.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A graph $G$ has vertices $A,B,C,D,E,F$ and nine edges: $AB$, $BC$, $CD$, $DE$, $EF$, $FA$, $AD$, $BE$ and $CF$.

   (a)

   What is the degree of each vertex of $G$?

   [1 mark]

   • A$3$
   • B$2$
   • C$4$
   • D$9$

   (b)

   Which two sets of vertices form a bipartition of $G$, with every edge joining the two sets?

   [1 mark]

   • A$\{A,B,C\}$ and $\{D,E,F\}$
   • B$\{A,B,D\}$ and $\{C,E,F\}$
   • C$\{A,C,D\}$ and $\{B,E,F\}$
   • D$\{A,C,E\}$ and $\{B,D,F\}$

   (c)

   Use Kuratowski's theorem to decide whether $G$ is planar.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A graph $H$ has vertices 1 to 7 and ten edges: 1–2, 1–6, 1–7, 4–7, 2–3, 3–4, 3–6, 2–5, 4–5 and 5–6.

   (a)

   Show that $H$ is a subdivision of $K_{3,3}$.

   [3 marks]

   (b)

   Deduce whether $H$ is planar. The graph $J$ is formed from $H$ by deleting vertex 7 and the two edges at it. Determine, with justification, whether $J$ is planar.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A student claims: '$K_5$ has 10 edges and is non-planar, so any graph with 10 or more edges is non-planar.' The graph $O$ has vertices $A,B,C,D,E,F$, and every pair of vertices is joined by an edge except $AB$, $CD$ and $EF$.

   (a)

   Show that $O$ has 12 edges. Describe how $O$ can be drawn with no edges crossing, and hence explain why the student's claim is false.

   [6 marks]

   (b)

   Using Kuratowski's theorem, explain why $K_{3,3}$ is non-planar. Hence evaluate the student's claim, and state what Kuratowski's theorem offers instead of counting edges.

   [6 marks]

   Total for question 4: 12 marks

End of questions