K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2011 · Q17
Time

Select one answerSingle correct
Solution
Official answer: B) Both K4 and Q3 are planar
Discrete MathematicsA graph is planar if it can be drawn in a plane without any of its edges crossing.
Graph (complete graph on 4 vertices): It has vertices and edges. can be drawn in the plane without edge crossings by placing one vertex inside the triangle formed by the other three and connecting it to all three vertices. Hence, is planar.
Graph (3-dimensional hypercube / 3-cube graph): It has vertices and edges. It is isomorphic to the 3D cube graph, which can be drawn as a planar graph (the standard Schlegel diagram of a cube: an inner square inside an outer square with corresponding vertices connected). Since it contains neither nor as a minor/subdivision, by Kuratowski's theorem, is planar.
Therefore, Both and are planar, making (B) the correct choice.
Try the question first, then check your work.
Examiner trap
Recall that a graph is planar if it can be redrawn on a 2D plane without any edge crossings. Try redrawing and the 3-cube as 2D figures.
This Discrete Mathematics previous year question is Q17 of the GATE CSE 2011 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 18 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2011.
How GATE tests Discrete MathematicsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.