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

Which one of the following graphs is NOT planar? A. G1 (Petersen-like graph with crossing edges) B. G2 C. G3 D. G4

GATE 2005 · Discrete Mathematics · Graph Planarity · medium

Answer: G1 is NOT planar. Answer: A. G1

  1. Apply edge bound to G1: G1 (Petersen): |V|=10, |E|=15. Bound: 3*10-6=24 >= 15. Bound not violated, so cannot conclude non-planarity from this alone.
  2. Apply Kuratowski's Theorem to G1: The Petersen graph (G1) contains a subdivision of K_{3,3}. It is a well-known non-planar graph. G2, G3, G4 are smaller graphs (resembling K4, K2,3 or wheel graphs) that are planar.