Bipartite planar graph edge bound

ID: bipartite-planar-graph-edge-bound

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with vertices, then . Every facial boundary walk has even length and length at least three, hence at least four. Thus ; substitute the Euler formula for a connected planar graph.[ref]
The square cycle graph attains equality: . The three-vertex graph path also attains equality: . 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.

New to topics? Read the docs here!