• S
    SwaseekhGATE Preparation
General
  • Dashboard
  • Syllabus
  • Questions
  • Aptitude
  • Mock Tests
  • TCS NQT 2026
Account
  • Pricing
  • Contact
  1. GATE CS
  2. PYQs
  3. Discrete Mathematics

K4 and Q3 are graphs with the following structures. K4 is the complete graph on 4 vertices. Q3 is the 3-dimensional hypercube graph (8 vertices, 12 edges). Which one of the following statements is TRUE in relation to these graphs? A. K4 is planar while Q3 is not B. Both K4 and Q3 are planar C. Q3 is planar while K4 is not D. Neither K4 nor Q3 is planar

GATE 2011 · Discrete Mathematics · Graph Planarity · medium

Answer: Both K4 and Q3 are planar.

  1. Verify K4 is planar: K4: |V|=4, |E|=6. Check: 6 <= 3*4-6 = 6. Satisfied (equality holds). K4 can be drawn as a triangle with an interior vertex connected to all three corners — a valid planar embedding.
  2. Verify Q3 is planar using the bipartite bound: Q3: |V|=8, |E|=12. Q3 is bipartite (parity of vertex labels splits into two sides), so girth = 4 (shortest cycle = 4). Check bipartite bound: 12 <= 2*8-4 = 12. Satisfied. Q3 has a planar embedding (draw two squares — inner and outer — with matching vertices connected).