Questions: Planar Graphs and Euler's Formula

Question 1

A student draws graph G in a particular way and produces 3 edge crossings. She concludes that G is non-planar. Is her reasoning valid?

• A. Yes — any drawing with crossings is sufficient evidence of non-planarity
• B. No — a graph is non-planar only if every possible drawing has crossings; one bad drawing proves nothing
• C. Yes — three crossings exceeds the planarity threshold
• D. No — only Kuratowski's theorem can establish non-planarity

Answer: (B)

Planarity is an existential property: a graph is planar if *some* crossing-free drawing exists. The fact that one particular drawing has crossings says nothing about whether a better drawing is possible. K₄ looks tangled in a naive square drawing but can be redrawn as a triangle with one interior vertex — no crossings. To prove non-planarity you must show that no crossing-free drawing exists, which is done via Euler's formula inequality (E > 3V − 6) or Kuratowski's theorem, not by exhibiting one bad drawing.

Question 2

A connected planar graph has V = 7 vertices and E = 11 edges. How many faces does it have?

• A. 4
• B. 5
• C. 6
• D. 7

Answer: (C)

Euler's formula for connected planar graphs states V − E + F = 2. Substituting: 7 − 11 + F = 2, so F = 6. This counts all faces, including the unbounded outer region surrounding the entire drawing. Forgetting to count the outer face is the most common error when applying this formula — it always counts as one face regardless of how large it is.

Question 3

A graph is non-planar if and mainly if it contains K₅ or K₃,₃ as a subgraph (not just a subdivision).

• T. True
• F. False

Answer: False

Kuratowski's theorem requires a *subdivision* of K₅ or K₃,₃, not the graphs themselves. A subdivision replaces each edge with a path through new degree-2 vertices. A graph can be non-planar while containing neither K₅ nor K₃,₃ as literal subgraphs — but it will always contain a subdivision of one of them. The distinction matters: subdivisions introduce extra vertices along edges, so the obstruction graphs can appear in disguised form.

Question 4

When Euler's formula V − E + F = 2 is applied to a planar graph drawn without crossings, the large unbounded region surrounding the entire drawing counts as one of the F faces.

• T. True
• F. False

Answer: True

The outer unbounded region is always counted as one face in Euler's formula. This is why a triangle (V=3, E=3) has F=2: one triangular face inside, plus the outer face. Students who forget this will compute F = 1 for a triangle and get V − E + F = 2, apparently satisfied — but only by luck of having undercounted F by exactly 1. For the formula to give consistent results across all planar graphs, the outer face must always be included.

Question 5

Explain how the inequality E ≤ 3V − 6 is derived from Euler's formula, and how it can prove a graph is non-planar without examining any specific drawing.

Model answer: In any planar graph, every face is bounded by at least 3 edges, and each edge borders at most 2 faces, so 3F ≤ 2E, giving F ≤ 2E/3. Substituting into V − E + F = 2 yields V − E + 2E/3 ≥ 2, which rearranges to E ≤ 3V − 6. If a graph violates this bound (E > 3V − 6), no planar drawing can exist — regardless of how cleverly you try to draw it.

The power of this approach is that it derives a necessary condition for planarity purely from counting, bypassing the need to reason about specific drawings. For K₅: V=5, so 3V−6=9, but E=10 > 9 — immediate contradiction. For K₃,₃: V=6, so 3V−6=12, but E=9 ≤ 12, so this bound alone doesn't rule out K₃,₃ (a tighter bound using the absence of triangles is needed). The inequality is a quick first test; Kuratowski's theorem provides the complete characterization.