Euler formula for a connected planar graph ($n-m+f=2$)

For a finite connected graph with at least one vertex, embedded as a plane graph, let $n$ count vertices, $m$ count edges, and $f$ count faces of a plane graph, including the outer face. ThenThe hypotheses refer to an actual embedding; regions in a crossing-filled graph drawing do not supply its $f$.^[ref]

In the plane graph $K_4$ pictured above, three bounded faces of a plane graph and the outer face give $4-6+4=2$. A square cycle graph gives $4-4+2=2$, while the graph path $A-B-C$ gives $3-2+1=2$. Changing a crossing into a new vertex changes the graph: the square-and-diagonals drawing then has five vertices, eight edges, and five faces of a plane graph, giving $5-8+5=2$.

A proof outline deletes edges on graph cycles. Each deletion preserves the connected graph and merges two faces of a plane graph, leaving $n-m+f$ unchanged. Eventually a tree remains, with $m=n-1$ and $f=1$. Adding the point at infinity identifies the plane picture with a sphere; the value two agrees with its Euler characteristic and the cell-count formula for Euler characteristic.

For a connected cellular spherical planar graph with vertex degrees at least three and face sizes at least three, degree/face double counting and the Euler formula for a connected planar graph give ${\sum }_n(6-n)F_n=12+{\sum }_m(2m-6)V_m\ge 12$. The left side is at most $3(F_3+F_4+F_5)$, proving the displayed bound. In particular a convex polyhedron has at least four faces of size at most five.

A finite simple graph that is a connected graph and a planar graph, with $n\ge 3$ vertices and $m$ edges, satisfies $m\le 3n-6$. Choose a plane graph: each facial boundary walk has length at least three, so $3f\le 2m$. Substitute $f=2-n+m$ from the Euler formula for a connected planar graph.^[ref]

The complete graph $K_4$ attains equality: $6=3\cdot 4-6$. The bound also holds for a disconnected finite simple graph that is a planar graph with $n\ge 3$: place its connected components of a graph in disjoint regions and join them with new bridges in a graph, then apply the connected bound.

If a finite simple graph is a connected graph, a bipartite graph, and a planar graph, with $n\ge 3$ vertices, then $m\le 2n-4$. Every facial boundary walk has even length and length at least three, hence at least four. Thus $4f\le 2m$; substitute the Euler formula for a connected planar graph.^[ref]

The square cycle graph attains equality: $4=2\cdot 4-4$. The three-vertex graph path also attains equality: $2=2\cdot 3-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.

The complete graph $K_5$ has $n=5$ and $m=\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, exceeding the planar graph edge bound $3\cdot 5-6=9$. Therefore it is not a planar graph. The complete bipartite graph $K_{3,3}$ has $n=6$ and $m=3\cdot 3=9$. The general bound allows twelve edges, but the bipartite planar graph edge bound allows only eight, proving nonplanarity.

These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every edge of $K_{3,3}$ once. The resulting simple graph is a connected graph with $n=15$, $m=18$, and is bipartite: put all original vertices in one part and all nine new vertices in the other. Both inequalities hold, $18\le 39$ and $18\le 26$. Nevertheless, a crossing-free graph drawing would let us trace each two-edge graph path as one curve, producing an impossible embedding of $K_{3,3}$. The graph subdivision preserves this obstruction. Kuratowski's theorem supplies a stronger characterization than these counts.

If every face of a connected planar graph has size at least $g>2$, double-counting edge-face incidences and using Euler's formula gives

Let a connected bridgeless planar graph have $n\ge 4$ vertices, $e$ edges, no four-cycle, and $t$ triangular faces. If no edge borders two triangular faces, thenso $f\le 8e/15$. The Euler formula for a connected planar graph then gives

The icosidodecahedral graph is the skeleton of the icosidodecahedron. It has 30 vertices, 60 edges, 20 triangular faces, and 12 pentagonal faces. Every edge separates a triangle from a pentagon, so it attains equality in the triangle-pentagon planar edge bound.