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.