A graph is planar if and only if, A. It does not contain a subgraph homeomorphic to K_5 and K_{3,3}. B. It does not cont...

Question

A graph is planar if and only if, A. It does not contain a subgraph homeomorphic to K_5 and K_{3,3}. B. It does not contain a subgraph isomorphic to K_5 and K_{3,3}. C. It does not contain a subgraph isomorphic to K_5 or K_{3,3}. D. It does not contain a subgraph homeomorphic to K_5 or K_{3,3}.

Accepted Answer

Only option D is correct. Kuratowski's theorem says a graph is planar exactly when it has NO subgraph that is a subdivision (a homeomorphic copy) of either K_5 or K_{3,3}. Two words must be exactly right: 'homeomorphic' (not merely 'isomorphic', because the forbidden graph may appear with extra degree-2 vertices placed along its edges) and 'or' (forbidding either one is enough). Only option D has both words correct.