= Bipartite planar graph edge bound
{title2=$m\leq2n-4$}
If a finite <simple graph> is a <connected graph>, a <bipartite graph>, and a <planar graph>, with $n\geq3$ <vertices>, then $m\leq2n-4$. Every <facial boundary walk> has even length and length at least three, hence at least four. Thus $4f\leq2m$; substitute the <Euler formula for a connected planar graph>.<Mathematics for Computer Science by Eric Lehman and others>[Mathematics for Computer Science, §12.5, Lemma 12.5.2 and Theorem 12.5.3, printed pp. 486–487]{ref}
The square <cycle graph> attains equality: $4=2\cdot4-4$. The three-<vertex> <graph path> also attains equality: $2=2\cdot3-4$. Its repeated <bridges in a graph> illustrate why counting <facial boundary walk> length correctly matters. Neither bound applies unchanged to a <multigraph>: two <vertices> may support arbitrarily many parallel <edges> in a <plane graph>.
Back to article page
