GATE CS 2011 Q17 — Graphs: Connectivity, Matching, Colouring

A graph is planar if it can be drawn in a 2D plane such that no two edges intersect (cross) each other except at their common vertices.

1. Analysis of $K_4$ (Complete graph on 4 vertices):

• $K_4$ has 4 vertices and 6 edges.
• We can draw $K_4$ without any edge crossings by placing three vertices to form an outer triangle and placing the fourth vertex inside this triangle, then connecting the inner vertex to the three outer vertices.
• Therefore, $K_4$ is planar.

2. Analysis of $Q_3$ (3-dimensional hypercube graph):

• $Q_3$ has 8 vertices and 12 edges.
• We can draw $Q_3$ in a 2D plane without any edge crossings by representing it as a smaller square nested inside a larger square, with their corresponding corners connected by non-intersecting edges.
• Therefore, $Q_3$ is planar.

Since both $K_4$ and $Q_3$ can be drawn without any edge crossings, both are planar graphs.