Kuratowski's theorem

Questions requiring proof that a graph is non-planar using Kuratowski's theorem (showing K_5 or K_3,3 subgraph).

4 questions · Challenging +1.3

7.02f Bipartite test: colouring argument
Sort by: Default | Easiest first | Hardest first
OCR Further Discrete 2023 June Q2
8 marks Challenging +1.8
2 A graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{c4755464-aa15-4720-8f33-5eb7169f4a20-2_522_810_1637_246}
  1. Write down a cycle through all six vertices.
  2. Write down a continuous route that uses every arc exactly once.
  3. Use Kuratowski's theorem to show that the graph is not planar.
  4. Show that the graph has thickness 2 .
AQA Further Paper 3 Discrete 2021 June Q6
8 marks Challenging +1.8
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.
Edexcel D1 Q1
6 marks Standard +0.3
  1. Draw the complete graph \(K_5\). [1 mark]
  2. Demonstrate that no planar drawing is possible for \(K_5\). [2 marks]
  3. Draw the complete graph \(K_{3,3}\). [1 mark]
  4. Demonstrate that no planar drawing is possible for \(K_{3,3}\). [2 marks]
OCR Further Discrete 2018 March Q4
12 marks Challenging +1.3
The graph below connects nine vertices A, B, \(\ldots\), H, I. \includegraphics{figure_2}
    1. Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9. [2]
    2. Explain what you can deduce from the result in part (a). [1]
  2. Use Kuratowski's theorem to prove that the graph is non-planar. [3]
  3. Prove that there is no subgraph of the graph that is isomorphic to \(K_4\), without using subdivision or contraction. [6]