GATE CS 1990 Q3-xi — Graphs: Connectivity, Matching, Colouring

According to Kuratowski's Theorem, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to (or an subdivision of) $K_5$ (the complete graph on $5$ vertices) or $K_{3,3}$ (the complete bipartite utility graph).

Let us analyze the logical structure of the statement:

• Let $P$ be the property "contains a subgraph homeomorphic to $K_5$".
• Let $Q$ be the property "contains a subgraph homeomorphic to $K_{3,3}$".

A graph is non-planar if it contains at least one of these subgraphs, i.e., $P \lor Q$.

Therefore, a graph is planar if and only if it is not non-planar:

This translates to: "It does not contain a subgraph homeomorphic to $K_5$ or $K_{3,3}$" (which is equivalent to saying it contains neither).

Why other options are incorrect:

• Option A: "Does not contain ... $K_5$ and $K_{3,3}$" ($eg(P \land Q)$) would mean a graph is planar as long as it does not contain both simultaneously. This is incorrect because containing just one of them is enough to make a graph non-planar.
• Options B & C: These options use "isomorphic" instead of "homeomorphic". Homeomorphism (which allows vertex insertion/subdivision) is the correct relation for Kuratowski's theorem.