Maximum number of edges in a planar graph with n vertices is ______

GATE 1992 · Discrete Mathematics · Graph Planarity · easy

Answer: Maximum edges = 3n - 6 (for n >= 3).

1. Each face needs >= 3 edges: Every face is bounded by at least 3 edges and each edge lies on exactly 2 faces, so 2E >= 3F, i.e. F <= 2E/3.
2. Combine with Euler's formula: F = 2 - V + E = 2 - n + E. Substitute into F <= 2E/3: 2 - n + E <= 2E/3 -> E/3 <= n - 2 -> E <= 3n - 6.