Prove that a simple planar bipartite graph on $n$ nodes has at most $2n-4$ edges. [closed]
Solution 1:
This is a very standard result in graph theory.
Theorem: If a connected planar graph with more than $3$ vertices has no cycles of length $3$, then $e \le 2v-4$.
Proof: From Euler's formula, we have $v-e+f=2$. Since there are no cycles of length $3$, every face has degree $4$ or greater. From the handshaking lemma, we then have $$4f \le \sum_{f\in F}\deg(f) = 2e$$ Substituting, we have $$2 = v-e+f \le v-e+\frac{e}{2}$$ which is the required result.