Kuratowski's theorem 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 or .
- How many vertices and edges does have?
- 5 vertices, 10 edges.
- How many vertices and edges does 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 planar?
- Yes: draw one vertex inside the triangle of the other three.
- What degrees must the five vertices have in a subdivision of ?
- At least 4 each in the graph.
- What degrees must the six vertices have in a subdivision of ?
- 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 itself, since needs 6 vertices.
- How do you prove a graph is non-planar?
- Find a subgraph that is a subdivision of or .
- How do you prove a graph is planar?
- Draw it with no crossings, or show it has no such subdivision.