Multiple choice general knowledge science & technology

According to Kuratowski's Theorem a graph G is planar if and only if G does not contain a subgraph homeomorphic to

  1. K5

  2. K5 or K4,4

  3. K3,3

  4. K5 or K3,3
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Kuratowski's theorem provides the complete characterization of planar graphs. A graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (complete graph on 5 vertices) or K3,3 (complete bipartite graph with 3+3 vertices). These two graphs are the minimal non-planar graphs - any graph containing them as a subgraph cannot be drawn without edge crossings.

Keep practicing — related questions