Problem
COM-B2-M07-P019 Planar Bipartite Graph
#19
★★★★★ Level 5 of 5
A simple connected planar bipartite graph has \(n\ge3\) vertices and \(m\) edges. Prove that \(m\le2n-4\).
A bipartite graph has no triangles, so every face has length at least \(4\).
Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). A bipartite graph has no odd cycles, in particular no triangles. Therefore every face boundary has length at least \(4\).
The sum of face boundary lengths is \(2m\), so \(4f\le2m\), i.e. \(f\le\frac{m}{2}\). Then \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Hence \(m\le2n-4\).
A strong planar bound often used to rule out \(K_{3,3}\).