Planar Graphs MCQs: 12 Solved Questions on Kuratowski’s Theorem, Homeomorphism and Edge Bounds

A drawing with crossed lines is not automatically a non-planar graph. You may be able to redraw the same adjacency without crossings. Likewise, the inequalities E <= 3V - 6 and E <= 2V - 4 are necessary tests, not complete characterisations.

Kuratowski’s theorem, homeomorphism, redraw tests, Euler’s formula, edge bounds and crossing numbers are key ideas in planar-graph problems. Select an option and write the decisive theorem or calculation before reading each explanation. Apply Euler’s formula and edge bounds in Questions 9, 10 and 11, then continue with the Planar Graphs Practice Questions hub.

Planar graph formulas and tests to use before the MCQs

Violating an applicable bound proves non-planarity. Satisfying it does not prove planarity.

Kuratowski’s theorem says that a graph is planar precisely when it contains no subdivision, or homeomorphic copy, of K_5 or K_{3,3}. Subdivision inserts degree-2 vertices into edges without removing the obstruction.

For K_5, V = 5 and E = 5 x 4 / 2 = 10, but the planar limit is 3(5) - 6 = 9. For K_{3,3}, V = 6 and E = 3 x 3 = 9; triangle-free planarity permits only 2(6) - 4 = 8. Both fail. Questions 3 and 4 also appear in the broader Graph Theory MCQ collection, where they support a survey of Euler paths, colouring and trees. Here they begin a focused progression through forbidden subdivisions, redraws, edge bounds and crossing numbers.

Kuratowski’s theorem MCQs 1-3: homeomorphism and the two forbidden graphs

Question 1: GATE Computer Science, 1990

A graph is planar if and only if,

• A. It does not contain subgraphs homeomorphic to K5 and K3,3.

• B. It does not contain subgraphs isomorphic to K5 or K3,3.

• C. It does not contain a subgraph isomorphic to K5 or K3,3.

• D. It does not contain a subgraph homeomorphic to K5 or K3,3.

Answer: D. It does not contain a subgraph homeomorphic to K5 or K3,3.

The obstruction is a homeomorphic copy, not only an isomorphic copy. Either K_5 or K_{3,3} is enough. A uses “and”, while B and C use the narrower “isomorphic”. Solved page.

Question 2: UGC NET Computer Science, December 2013

A graph is non-planar if and only if it contains a subgraph homomorphic to

• A. K3, 2 or K5

• B. K3, 3 and K6

• C. K3, 3 or K5

• D. K2, 3 and K5

Answer: C. K3, 3 or K5.

The theorem says “homeomorphic”, meaning a subdivision of K_{3,3} or K_5. Question 2 preserves the source word “homomorphic”, but homeomorphic is the standard term. K_{2,3} is planar, while K_6 is not a Kuratowski obstruction. Only C gives the correct pair with “or”. Solved page.

Question 3: GATE Computer Science, 2007

Let G be the non-planar graph with the minimum possible number of edges. Then G has

• A. 10 edges and 6 vertices

• B. 10 edges and 5 vertices

• C. 9 edges and 6 vertices

• D. 9 edges and 5 vertices

Answer: C. 9 edges and 6 vertices.

K_{3,3} has 3 x 3 = 9 edges and six vertices; K_5 has 5 x 4 / 2 = 10 edges and five. Subdivision adds edges, so nine is minimal. Solved page.

Planar graph MCQs 4-6: redraw crossings before declaring non-planarity

Question 4: GATE Computer Science, 2011

K4 and Q3 are graphs with the following structures.

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

• A. K4 is a 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

Answer: B. Both K4 and Q3 are planar.

Draw K_4 as a triangle with one vertex inside and three spokes: V = 4, E = 6, F = 4. Draw Q_3 as nested squares with matching corners joined: V = 8, E = 12, F = 6. Euler gives 2 in both, with no crossing. Solved page.

Question 5: GATE Computer Science, 1989

Which of the following graphs is/are planner?

• A. G1 only

• B. G1 and G2

• C. G2 only

• D. G2 and G3

Answer: C. G2 only.

The source spelling “planner” asks about planarity. G1 and G3 each have the six vertices and nine adjacencies of K_{3,3}. Redraw cube-style G2 as nested squares with corresponding corners joined. Only G2 has a crossing-free embedding. Solved page.

Question 6: GATE Computer Science, 2005

Which one of the following graphs is NOT planar?

• A. G1

• B. G2

• C. G3

• D. G4

Answer: A. G1.

G1 is triangle-free K_{3,3}, with V = 6 and E = 9, but planarity requires E <= 2V - 4 = 8. For G2, G3 and G4, route the displayed crossing edge through the outer face without changing its endpoints. Each then has a crossing-free redraw. Solved page.

Planar graph MCQs 7-8: identify a hidden obstruction in a figure

Question 7: UGC NET Computer Science, 2021

Which of the following Graph is(are) planar?

• A. A and B only

• B. B and C only

• C. A only

• D. B only

Answer: A. A and B only.

Graphs A and B redraw without crossings by putting an outer cycle and the remaining edges in separate faces. For C, reverse the subdivisions by suppressing the degree-2 vertices, leaving six branch vertices. These six vertices split into two groups of three, and every one of the nine pairs across the groups is joined. This exposes a subdivision of K_{3,3}, so C is non-planar. The crossings drawn in the source figure by themselves prove nothing. Solved page.

Question 8: UGC NET Computer Science, June 2012

G1 and G2 are two graphs as shown in figure?

• A. Both G1 and G2 are planar graphs

• B. Both G1 and G2 are not planar graphs

• C. G1 is planar and G2 is not planar

• D. G1 is not planar and G2 is planar

Answer: D. G1 is not planar and G2 is planar.

G1 has bipartition {a, d, f} and {b, c, e}, with every cross-set pair joined, so it is K_{3,3}. For G2, draw a four-cycle, place one vertex inside and one outside, and join each to all four cycle vertices. This double fan has V = 6, E = 12, and F = 8. The equality E = 3V - 6 is consistent; the redraw proves planarity. Solved page.

Euler formula MCQs 9-11: edge bounds and triangular faces

Regions, face degrees, polyhedra and derived bounds receive a formula-first treatment in Euler Formula for Planar Graphs MCQs. Use Questions 9-11 here only as planarity screens after the Kuratowski and redraw problems.

Question 9

Consider a graph G to be connected planar graph with 10 vertices. Which of the following can be number of edges in graph G order to be G be connected?

• A. 22

• B. 23

• C. 24

• D. 25

Answer: A, B and C. This is a multiple-select question (MSQ), so more than one option is correct.

Despite its garbled wording, the source stem asks which edge counts keep G a simple connected planar graph on 10 vertices. Connectivity needs at least V - 1 = 9 edges, while simple planarity allows at most 3V - 6 = 24. Thus 9 <= E <= 24: 22, 23 and 24 can occur, but 25 cannot.

Question 10

Let G be a connected planar graph with 10 vertices. If the number of edges one each face is three, then the number of edges in G is

• A. 24

• B. 34

• C. 32

• D. 56

Answer: A. 24.

Triangular faces give 3F = 2E, so F = 2E/3. Euler becomes 10 - E + 2E/3 = 2. Multiply by three: 30 - 3E + 2E = 6, hence E = 24. Cross-check: 3V - 6 = 24.

Question 11

Which of the following cannot be the number of edges in a simple planar graph with n = 15 vertices?

• A. 30

• B. 32

• C. 36

• D. 42

Answer: D. 42.

The bound is E <= 3V - 6 = 3(15) - 6 = 39. Since 42 > 39, 42 is impossible. A 15-vertex planar tree can be augmented one noncrossing edge at a time to a maximal planar graph with 39 edges, so 30, 32 and 36 are attainable totals.

Crossing-number MCQ 12: order complete and complete bipartite graphs

Question 12: UGC NET Computer Science, January 2026

If K_n is a complete simple graph of n vertices and K_m,n is a complete bipartite graph, then arrange the following non-planar graphs in ascending order on the basis of the minimum number of crossings.

A. K_6

B. K_7

C. K_4,4

D. K_5,5

Choose the correct answer from the options given below:

1. A, B, C, D

2. C, D, A, B

3. A, C, B, D

4. B, D, A, C

• A. 1

• B. 2

• C. 3

• D. 4

Answer: C. 3, corresponding to A, C, B, D.

The minima are cr(K_6) = 3, cr(K_{4,4}) = 4, cr(K_7) = 9, and cr(K_{5,5}) = 16. Therefore 3 < 4 < 9 < 16 gives A, C, B, D, numbered choice 3 and outer option C. Solved page.

Planar graphs MCQ answer check and next step

Use your errors diagnostically:

• Theorem-wording errors point to homeomorphism and the word “or”.

• Figure errors point to crossing-free redraws and subdivision recognition.

• Numerical errors point to Euler’s formula or the applicable edge bound.

• A Question 12 error points to crossing-number recall.

The key skills are reading theorem wording, recognising hidden K_{3,3}, finding crossing-free redraws, checking Euler arithmetic and applying crossing-number results. Repeat any missed item before moving on.

If you want the wider GATE CS syllabus sequenced, continue with GATE Guidance by Sanchit Sir. To strengthen planarity, repeat the questions without looking at the answer grid, then use the Planar Graphs Practice Questions hub.