Motivation
A graph can be drawn in many ways. Crossings in one drawing may be an artifact of the drawing rather than a property of the graph. Planarity asks whether some drawing avoids crossings between edges except at common endpoints. A face-counting identity turns such a geometric existence question into arithmetic constraints on vertices and edges. We work with finite simple undirected graphs and distinguish a graph from a particular embedding of it.
Definitions
Definition 3.1.1
(Plane embeddings, planar graphs and faces)
A plane embedding draws each edge as a simple arc between its endpoints, with distinct edges meeting only at common endpoints and no vertex lying inside an edge. A graph is planar if it has a plane embedding. The connected regions of the plane left after removing the drawing are its faces, including the unbounded outer face.
A graph may have different embeddings and drawings: the chosen outer face is not an intrinsic vertex or edge of the abstract graph.
For a disconnected drawing, define the length of a face boundary as the total number of incident edge sides over all its boundary components, counting a bridge twice when both sides meet that face. An isolated vertex contributes no edge side.
Definition 3.1.2
(Proper coloring and chromatic number)
A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number is the smallest number of colors in a proper coloring.
Isolated vertices impose no constraints on other vertices. The existence of a planar drawing and the number of colors in a coloring are distinct questions, although planarity can help provide coloring bounds.
Theorem/proposition
Theorem 3.1.3
(Euler's formula for connected plane graphs)
For a finite connected plane graph with vertices, edges and faces, .
Theorem 3.1.4
(Simple planar edge bound)
For a finite simple connected planar graph with , the number of edges satisfies .
Concept lensCombinatorial
Bounded faces count the edges outside a spanning tree
Rewrite the formula as . A spanning tree of a connected graph has edges, so the right side counts the edges outside the tree, which is also the number of fundamental cycles that tree determines. The proof below realizes this count step by step: each deleted cycle edge lies outside the spanning tree that finally remains, and each deletion removes one bounded face. Hence the number of bounded faces is the same in every plane embedding of the graph, although their shapes may differ.
Proof sketch or proof idea
Proof
(Deleting cycle edges down to a spanning tree)
We use the Jordan curve theorem: a simple closed curve in the plane separates it into an inside and outside, with the curve as their common boundary. First suppose the connected graph is a tree. It has , and a plane drawing of a tree has one face: starting from a single vertex, adding a leaf edge cannot enclose a region, because the new edge does not form a closed curve. Therefore .
If the graph is not a tree, select an edge on a cycle. Deleting it preserves connectedness: the rest of the cycle supplies an alternate path between its endpoints. In the plane drawing the edge separates two different faces; a path along the remaining part of its cycle together with the edge forms a simple closed curve, putting its two local sides in different components of the complement. Deleting the edge merges exactly those two faces. Thus both and decrease by one, leaving unchanged. Repeat until a spanning tree remains. Finiteness ensures that the process stops, and the tree case proves the identity.
Proof X-ray
Where the plane enters the proof
The counting is trivial; the topology sits in two places. The tree case uses that adding a leaf edge cannot enclose a region, because a new arc meeting the drawing at only one endpoint lies on no closed curve. The step uses the Jordan curve theorem exactly once: an edge on a cycle, together with the rest of that cycle, is a simple closed curve, so its two sides lie in different faces and deleting it lowers by exactly one. Choosing an edge on a cycle is what makes both halves work, since it keeps the graph connected while guaranteeing two distinct faces; deleting a bridge would leave unchanged and disconnect the graph. Finiteness stops the deletions, and connectedness is the hypothesis that makes the end point a spanning tree with .
Proof
(Counting edge sides)
For the edge bound, count the face incidences of edges. Every edge has two sides and contributes two to the sum of face-boundary lengths, even when a bridge occurs twice on the same boundary. In a connected simple plane graph with at least three vertices every face boundary has length at least three: a one-edge boundary would be a loop, and a two-edge boundary would either consist of parallel edges or traverse the sole edge of a two-vertex component twice. Thus . Euler's formula gives , so and .
Counterexample mode
Simplicity and three vertices are both needed
Claim: every connected planar graph with satisfies , simple or not. Draw a triangle and double each edge by a second arc beside it, outside the triangle. This connected plane multigraph has and , and Euler's formula gives : the inner triangular face, the outer face and three faces of length two between parallel arcs. But . Faces of length two are exactly what simplicity excludes. The vertex condition is needed as well: a single edge has , while at . Euler's identity itself holds in both cases; only the face-length bound fails.
Worked examples
Worked example 3.1.5
(the complete graph on five vertices)
The complete graph has five vertices and one edge for each pair, so . A simple connected planar graph on five vertices has at most edges. The contradiction proves is nonplanar. We did not need to inspect every possible drawing.
Worked example 3.1.6
(a square with a diagonal)
A square together with one diagonal has and . Draw its diagonal inside the square: there are two bounded triangular faces and one unbounded face, so and . The ordinary edge bound gives , as expected. The inequality alone does not construct the embedding; the drawing supplies it.
Worked example 3.1.7
(a tree in the plane)
A path on four vertices has three edges and one face, so . Its single face has boundary length six when edge sides are counted with multiplicity: each of the three bridge edges is encountered on both sides. Treating each edge as contributing to two different faces would give the wrong count.
Common mistakes
Counterexample mode
A necessary bound is not a planarity test
The inequality is necessary, not sufficient, for planarity. For example has and , so it satisfies , yet it is nonplanar, as a sharper argument below proves. A graph can also be planar even if a particular drawing has crossings: the square with both diagonals crossed is , which has a crossing-free embedding with one vertex inside a triangle.
Common mistake
(Euler's formula needs the number of components)
For two separate triangles, , not . Applying to a disconnected drawing would predict only faces and miss one triangle interior. The correct constant is , as proved in the section on disconnected drawings.
Common mistake
(A bridge has two sides on the same face)
In the four-vertex path the single face has boundary length six, not three: each of the three edges is met on both of its sides. Counting each bridge once would make the face lengths sum to , contradicting the identity that they sum to , on which every edge bound in this note depends.
Summary
Euler's identity concerns a fixed plane embedding; the edge bounds are consequences for abstract planar graphs. Their hypotheses matter, and failure of a necessary bound proves nonplanarity, while passing a bound does not prove planarity. Count edge sides with multiplicity when bridges occur.
Exercises
Quick check
(A connected plane graph has vertices and edges. How many faces does it have?)
Solution · Answer
Euler's formula gives , including the outer face.
Quick check
(Can a simple connected planar graph with vertices have edges?)
Solution · Answer
No. The bound requires .
A stronger bound for bipartite graphs
Definition 3.1.8
(Bipartite graph)
A graph is bipartite if its vertices can be partitioned into two sets so that every edge joins the sets.
Theorem 3.1.9
(Bipartite planar edge bound)
For a finite simple connected bipartite planar graph with , .
Proof
(Faces of length at least four)
Traversing an edge switches sides, so every closed walk has even length. In a connected simple bipartite plane graph with at least three vertices, every face boundary has length at least four: the previous argument rules out lengths one and two, and bipartiteness rules out odd length. This remains true when a boundary walk repeats a bridge.
Counting edge sides now gives . Substituting yields
For , the two sets each have three vertices and every cross-pair is an edge. Thus and , while the bound would give . Hence is not planar. The usual bound did not detect this obstruction; the extra hypothesis of bipartiteness improves the conclusion.
The face-length hypothesis is doing the work, not the name bipartite by itself. If a connected simple plane graph has every face boundary of length at least , then , and Euler's formula gives
The meaning of length must include repeated edge sides for bridges. One should not substitute a claimed girth into this formula without checking the corresponding face-boundary condition, especially for trees, which have no cycles but do have a face boundary walk.
Quick check
(Could a connected simple bipartite planar graph with vertices have edges?)
Solution · Answer
No: the bipartite bound gives . This proves impossibility for all plane drawings, not just for one attempted picture.
Coloring by an ordering
There is a simple coloring bound that does not need planarity. Let be the largest vertex degree in a finite nonempty graph. Order the vertices arbitrarily and color them one at a time from a palette of colors. When a vertex is reached, at most of its neighbors have already been colored, so at most colors are forbidden. At least one color remains. Consequently .
The complete graph shows this bound can be tight: every pair of its vertices is adjacent, so no two can share a color. On a particular graph, a different order can give a different number of colors even though the same upper bound remains valid. A greedy coloring is therefore a certificate that a certain number of colors suffices, not in general proof that the number is minimal.
Example. A four-vertex path has maximum degree two, so the general bound gives at most three colors. Alternating two colors along the path gives a coloring with two. One color is impossible because there is an edge. Thus its chromatic number is two, and the maximum-degree bound is not sharp for this graph.
For planar graphs the celebrated four-color theorem gives a stronger universal upper bound, but its proof is not supplied here and cannot be inferred merely by applying the degree bound. A finite nonempty simple planar graph has a vertex of degree at most five. For every degree is at most one. For , use the disconnected extension of proved below: the degree sum is , so not every degree can be at least six. Turning that observation into a four-color proof requires additional ideas; it does not follow just from this averaging step.
Quick check
(Show that a nonempty forest with at least one edge is 2-colorable and has chromatic number exactly .)
Solution · Answer
In each tree choose a root and color vertices by the parity of their distance from it. Every edge joins consecutive levels: if an edge joined two vertices whose root distances had the same parity, the unique root paths together with that edge would create a cycle. Thus adjacent vertices have different colors. Isolated vertices can receive either color. At least one edge has endpoints requiring different colors, so one color is impossible.
Quick check
(A planar drawing has , , and all faces have boundary length four. How many faces are there?)
Solution · Answer
No such drawing exists. Each edge has two sides, so the face-boundary lengths sum to . If every face has length four, that sum is , and has no integer solution. The argument uses neither Euler's formula nor connectedness. Applying the connected formula regardless would predict faces, whose lengths would sum to .
Disconnected drawings
Connectedness is essential in the stated form of Euler's formula.
Theorem 3.1.10
(Euler's formula with components)
For a plane graph with connected components,
Proof
(Joining the components by bridges)
One way to see this is to add edges joining distinct components in the plane, without introducing crossings. Each added edge is a bridge, so it does not create a new face. The resulting connected plane graph has the same vertices and faces and edges. Applying the connected formula and rearranging proves the identity. The connecting arcs can be drawn inside faces between components; when a component lies inside another component's cycle, begin by connecting it through the face containing it to the boundary of that face. Repeat until all components are joined.
For instance, two separate triangles have , , and : one outside face and one inside each triangle. Thus . Substituting 2 for the right-hand side would be incorrect. An isolated vertex is a component but does not create a new face; adding one increases both and by one, leaving the identity consistent.
When using an edge bound, separate out small or disconnected cases instead of inserting their values blindly into a proof for connected graphs. The familiar simple-planar bound does extend to simple planar graphs with , since additional noncrossing edges can connect components and, if necessary, extend the drawing to a connected simple planar graph on the same vertices. An edge joining two different components is never parallel to an existing edge, so the enlarged graph is still simple, and the connected bound applied to it gives . The face-counting derivation above assumed connectedness; this edge-adding step is what justifies the disconnected case.