Questions: Planar Graphs, Euler's Formula, and Structure

Question 1

A simple connected graph has 8 vertices and 22 edges. Without drawing it, what can you conclude?

• A. It is planar, because 22 edges is not too many for 8 vertices
• B. It is non-planar, because E = 22 > 3(8) − 6 = 18, violating the necessary condition for planarity
• C. It might be planar — you would need to try all possible drawings to be sure
• D. It is non-planar, because Kuratowski's theorem applies to all graphs with more than 20 edges

Answer: (B)

The inequality E ≤ 3V − 6 is a necessary condition for planarity of a simple graph. For V = 8, the bound is 3(8) − 6 = 18. Since 22 > 18, the graph cannot be planar — the arithmetic proof is sufficient, no drawing attempts needed. Option C reflects the misconception that planarity can only be determined by exhaustive drawing; Euler's formula gives us a way to rule it out algebraically.

Question 2

A graph G looks like it requires edge crossings in every drawing you attempt. What does this tell you about whether G is planar?

• A. G is definitely non-planar — if all attempted drawings have crossings, no crossing-free drawing can exist
• B. Nothing definitive — planarity means there EXISTS some drawing without crossings, and you may not have found it yet
• C. G is planar if the edge crossings can be reduced to fewer than V crossings
• D. G is non-planar only if it fails both Euler's inequality and Kuratowski's theorem simultaneously

Answer: (B)

Planarity is a property of the abstract graph: does there exist ANY drawing without crossings? The fact that several attempts all produce crossings is not proof of non-planarity. The Explainer gives K₄ as an example — it looks like it needs a crossing, but a redrawing with the fourth vertex inside a triangle shows it is planar. To prove non-planarity, you need either the edge-count inequality or Kuratowski's theorem, not just failed drawing attempts.

Question 3

In Euler's formula V − E + F = 2 for connected planar graphs, the unbounded outer region counts as a face.

• T. True
• F. False

Answer: True

This is essential and explicit in the Explainer. For a triangle, V=3, E=3, F=2 — the two faces are the triangular interior region and the unbounded exterior region. If you forgot the outer face, you would get F=1 and the formula would give 3 − 3 + 1 = 1 ≠ 2. Always including the outer region is required for Euler's formula to hold.

Question 4

K₅ is non-planar because every possible drawing of it in the plane produces at least one edge crossing.

• T. True
• F. False

Answer: True

This is actually true and consistent with the topic, but the important nuance is *why*: K₅'s non-planarity is not just an empirical observation from failed drawing attempts — it is provable from the edge-count inequality. K₅ has V=5, E=10, and 3V−6=9, so E > 3V−6, which violates the necessary condition for planarity. This algebraic proof guarantees that no drawing without crossings can exist, which is a stronger and more general claim than 'we've tried many drawings.'

Question 5

How does Euler's formula allow you to prove that K₅ is non-planar without trying all possible drawings?

Model answer: Euler's formula implies a necessary inequality for planar graphs: E ≤ 3V − 6 (since every face is bounded by at least 3 edges, and each edge borders at most 2 faces, giving 3F ≤ 2E; substituting F = 2 − V + E yields E ≤ 3V − 6). K₅ has V=5 and E=10, but 3(5)−6=9 < 10. Since K₅ violates this necessary condition, it cannot be planar — regardless of how it is drawn.

This is the payoff of Euler's formula: it turns a topological/geometric question (can this graph be drawn without crossings?) into an algebraic inequality that can be checked in seconds. The key conceptual move is deriving the edge bound from the face-edge relationship and then substituting Euler's formula to eliminate F. Kuratowski's theorem then gives the converse: not just that K₅ fails this test, but that every non-planar graph contains K₅ or K₃,₃ as a subdivision.