Skip to interview prep
Apexed

242. What is Euler's formula for planar graphs, and how many faces does K(2,3) have?

MediumGraph algorithms

Technical
Show model answer

A connected planar graph drawn without crossings satisfies V − E + F = 2, where F counts faces including the unbounded outer face. K(2,3) is planar with V = 5 and E = 6, so F = 2 − 5 + 6 = 3.

Consequences: a simple planar graph with V ≥ 3 has E ≤ 3V − 6 (and E ≤ 2V − 4 if it has no triangles). K5 has 10 > 9 edges and K(3,3) has 9 > 8 edges, so neither is planar; Kuratowski's theorem says a graph is planar iff it contains no subdivision of K5 or K(3,3). Planarity can be tested in linear time.

What is Euler's formula for planar graphs, and how many faces does K(2,3) have — Data structures & algorithms interview question — Apexed