Planar bipartite bound

#bipartite#planar#edge bound

Statement

Show that a planar bipartite graph with $v\ge3$ has $e\le2v-4$ .

Hint

Faces have $\ge4$ edges, so $4f\le2e$ .

Show solutionHide solution

Face bound. $4f\le2e$ , so $f\le e/2$ .

Euler. $v-e+f=2$ , so $f=2-v+e\le e/2$ , i.e. $4-2v+2e\le e$ , giving $e\le2v-4$ .

Conclusion. Bipartite planar graphs satisfy $e\le2v-4$ .