Problem
COM-B2-M07-P017 Planar Bound
#17
★★★★☆ Level 4 of 5
A simple connected planar graph has \(n\ge3\) vertices and \(m\) edges. Prove that \(m\le3n-6\).
Use Euler's formula and the fact that every face has length at least \(3\).
Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). Since the graph is simple and \(n\ge3\), every face is bounded by at least three edges. In the sum of face boundary lengths, every edge is counted twice, so \(3f\le2m\).
Thus \(f\le\frac{2m}{3}\), and \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Hence \(m\le3n-6\).
The planar bound is needed for impossibility problems about crossing-free drawings.