Kuratowski's theoremAQA A-Level Further Maths: Flashcards

What these 14 flashcards ask

What is a planar graph?
State Kuratowski's theorem.
How many vertices and edges does K5 have?
How many vertices and edges does K{3,3} have?
What is a subdivision of a graph?
What does it mean to suppress a vertex?
Does subdividing an edge change planarity?
Is K4 planar?
What degrees must the five vertices have in a subdivision of K5?
What degrees must the six vertices have in a subdivision of K{3,3}?
What can you say about a graph with at most 8 edges?
A graph has exactly 5 vertices. When is it non-planar?
How do you prove a graph is non-planar?
How do you prove a graph is planar?

Exam questions on Kuratowski's theorem

The complete graph $K_5$ has five vertices, each joined to every other vertex.
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
A graph $G$ has vertices $A,B,C,D,E,F$ and nine edges: $AB$ , $BC$ , $CD$ , $DE$ , $EF$ , $FA$ , $AD$ , $BE$ and $CF$ .
Use Kuratowski's theorem to decide whether $G$ is planar.2 marks
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.
Show that $H$ is a subdivision of $K_{3,3}$ .3 marks

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).