GATE CS 2011 Q.17 (CS Q.17): Graph Theory

$K_4$ and $Q_3$ are graphs with the following structures.

Which one of the following statements is TRUE in relation to these graphs?

$K_4$ is planar while $Q_3$ is not

Both $K_4$ and $Q_3$ are planar

$Q_3$ is planar while $K_4$ is not

Neither $K_4$ nor $Q_3$ is planar

Official answer and solution

Solution

Recall planar graph characterizations and embed $K_4$ and $Q_3$ in the plane without crossing edges.

A graph is planar if it can be drawn in the plane such that no two edges intersect except at their common vertices.

For $K_4$ (complete graph on 4 vertices): A standard planar embedding places 3 vertices as an outer triangle and the 4th vertex inside, connected to all 3 outer vertices. No edges cross, so $K_4$ is planar.

For $Q_3$ (the 3D cube graph with 8 vertices and 12 edges): A planar embedding is obtained by drawing a large outer square (4 vertices) enclosing a smaller concentric inner square (4 vertices), and connecting corresponding vertices by 4 radial edges without crossings.

By Kuratowski's theorem, neither graph contains a subgraph homeomorphic to $K_5$ or $K_{3,3}$ . Both $K_4$ and $Q_3$ are planar graphs.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.