A graph is non-planar if and only if it contains a subgraph homomorphic to
2013
A graph is non-planar if and only if it contains a subgraph homomorphic to
- A.
K3, 2 or K5
- B.
K3, 3 and K6
- C.
K3, 3 or K5
- D.
K2, 3 and K5
Attempted by 231 students.
Show answer & explanation
Correct answer: C
Answer: A graph is non-planar if and only if it contains a subgraph homeomorphic to K3,3 or K5.
Explanation (Kuratowski's theorem):
Kuratowski's theorem states that a finite graph is non-planar exactly when it contains a subdivision (a homeomorphic copy) of K5 or K3,3.
Homeomorphic (a subdivision) means you may replace edges by paths by inserting degree-2 vertices; the resulting graph preserves the same connectivity pattern as the original.
K5 is the complete graph on five vertices and K3,3 is the complete bipartite graph with partitions of size three; these two are the minimal forbidden subdivisions for planarity, so every non-planar graph contains a subdivision of one of them.
Other graphs mentioned in the choices (for example K2,3 or K6) are not the correct characterization: K2,3 is not one of the two Kuratowski obstructions, and K6, while non-planar, is not required as a subdivision in every non-planar graph.
Therefore the correct characterization is: a graph is non-planar iff it contains a subgraph homeomorphic to K3,3 or K5.