Kuratowski's theorem

Kuratowski's theorem Flashcards

Spec DA4 · AQA A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

14 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 14 cards
What is a planar graph?
A graph that can be drawn in the plane with no edges crossing.
State Kuratowski's theorem.
A graph is non-planar if and only if it contains a subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}.
How many vertices and edges does K5K_5 have?
5 vertices, 10 edges.
How many vertices and edges does K3,3K_{3,3} have?
6 vertices, 9 edges.
What is a subdivision of a graph?
A graph formed by inserting new vertices of degree 2 into the edges.
What does it mean to suppress a vertex?
Remove a degree-2 vertex and join its two neighbours by one edge.
Does subdividing an edge change planarity?
No: a graph is planar if and only if its subdivision is planar.
Is K4K_4 planar?
Yes: draw one vertex inside the triangle of the other three.
What degrees must the five vertices have in a subdivision of K5K_5?
At least 4 each in the graph.
What degrees must the six vertices have in a subdivision of K3,3K_{3,3}?
At least 3 each in the graph.
What can you say about a graph with at most 8 edges?
It is planar: a subdivision of either Kuratowski graph needs at least 9 edges.
A graph has exactly 5 vertices. When is it non-planar?
Only if it is K5K_5 itself, since K3,3K_{3,3} needs 6 vertices.
How do you prove a graph is non-planar?
Find a subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}.
How do you prove a graph is planar?
Draw it with no crossings, or show it has no such subdivision.

Flashcards