Euler Bounds as Tests
Euler’s formula gives necessary conditions for a graph to be planar. In practice, these conditions let us reject some candidate graphs using only their number of vertices and edges. The logic has an important asymmetry: if the counts violate a valid planar bound, the graph is nonplanar; if they satisfy the bound, the test has not established that the graph is planar.
All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A graph is planar if it can be drawn in the plane with no edges crossing except at common endpoints. A particular such drawing is a plane embedding. For a graph \(G=(V,E)\), its order is \(n=|V|\) and its size is \(m=|E|\). The bounds below concern planarity, so they do not depend on a particular embedding.
The hypotheses matter. The ordinary simple planar bound applies when \(n\ge3\). A stronger bound applies when the graph is also bipartite, meaning its vertices can be divided into two sets so that every edge joins the sets. That stronger test must not be used unless bipartiteness has been established.
The Two Bounds
Proof. First suppose \(G\) is connected and take a plane embedding. Let \(f\) be its number of faces. Euler’s formula gives \(n-m+f=2\). Count the lengths of all facial boundary walks, counting an edge twice if it occurs on two sides of the same face. Each edge contributes two sides, so the sum of the lengths is \(2m\). Every facial boundary walk has length at least \(3\): length \(1\) would require a loop, while a boundary walk of length \(2\) in a connected simple graph would force the entire graph to be a single edge, contrary to \(n\ge3\). Thus \(3f\le2m\). Substituting \(f=2-n+m\) gives \(3(2-n+m)\le2m\), hence \(m\le3n-6\).
If \(G\) is disconnected, draw its components in disjoint regions and join them one at a time by arcs in the unbounded face. This produces a connected simple planar graph on the same \(n\) vertices, with at least as many edges as \(G\). The connected case bounds that larger edge count by \(3n-6\), so \(G\) also satisfies the bound. \(\square\)
Proof. Suppose first that \(G\) is connected and take a plane embedding. Each facial boundary walk has even length: as the walk follows edges, it alternates between the two parts of the bipartition and must return to its starting part. A facial boundary walk cannot have length \(2\) unless the connected graph consists of a single edge: in a simple graph the walk would traverse the same edge in both directions, and for that to be the entire face boundary at both ends, both endpoints must have degree \(1\). This contradicts \(n\ge3\). Therefore every face has boundary length at least \(4\). Counting edge sides gives \(4f\le2m\). Using Euler’s formula \(f=2-n+m\), we obtain \(4(2-n+m)\le2m\), and hence \(m\le2n-4\).
For a disconnected bipartite graph, draw the components separately and join them successively by edges in the unbounded face. Before adding each edge, if necessary, swap the two parts of one component so that the new edge joins opposite parts. This keeps the graph simple, planar, and bipartite. The connected case gives the bound for the enlarged graph on the same \(n\) vertices; since it has at least as many edges as the original graph, the original also satisfies \(m\le2n-4\). \(\square\)
Both bounds are necessary conditions, not characterizations. The first is broader; the second is stronger but has the additional bipartite hypothesis. For \(n<3\), use a separate direct check rather than these formulas: a simple graph on one vertex has no edges, and a simple graph on two vertices has at most one edge.
Applying the Test
Record its vertex set and edge set, or give an equally precise description of its edges.
Compute \(n\) and \(m\), showing how the edge count was obtained.
Confirm simplicity and \(n\ge3\). Use the bipartite bound only after confirming bipartiteness.
If \(m\) exceeds the applicable bound, conclude nonplanarity. Otherwise, report that this test does not decide planarity.
Worked Example: The Ordinary Bound Rejects \(K_5\)
Let \(G=K_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,14,15,23,24,25,34,35,45\}\). Test whether the ordinary bound rules out planarity.
There are \(n=5\) vertices. The listed edges are all the pairs of distinct vertices, so there are \(m=\binom{5}{2}=5\cdot4/2=10\) edges. The simple planar bound would require \(m\le3n-6=3\cdot5-6=15-6=9\). But \(10>9\), so \(K_5\) is nonplanar.
Check: The comparison uses \(n=5\ge3\), and the graph is simple, so the theorem applies. The inequality fails by \(10-9=1\) edge; no drawing or face count for a proposed embedding is needed.
Worked Example: The Bipartite Bound Rejects \(K_{3,4}\)
Let \(G=K_{3,4}\), with vertex set \(V=\{a_1,a_2,a_3,b_1,b_2,b_3,b_4\}\) and edge set \(E=\{a_i b_j:1\le i\le3,\ 1\le j\le4\}\). Decide whether the bipartite bound rules out planarity.
The two displayed vertex groups form a bipartition: every edge joins an \(a_i\) to a \(b_j\), and there are no other edges. Thus \(G\) is bipartite. Its order is \(n=3+4=7\). Each of the three \(a_i\) is joined to four vertices, giving \(3\cdot4=12\) distinct edges, so \(m=12\). The bipartite planar bound would require \(m\le2n-4=2\cdot7-4=14-4=10\). Since \(12>10\), \(G\) is nonplanar.
Check: The ordinary bound gives \(3n-6=3\cdot7-6=21-6=15\), and \(12\le15\), so that weaker test alone would not reject the graph. The bipartite bound does reject it, and its hypothesis has been verified directly from the edge set.
Worked Example: Passing a Bound Is Not a Proof of Planarity
Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61,14\}\). This is a 6-cycle with one additional edge. Test the counts, and then verify planarity separately.
The vertex set has \(n=6\) elements, and the edge set lists seven distinct edges, so \(m=7\). The ordinary bound is \(3n-6=3\cdot6-6=18-6=12\), and \(7\le12\). The graph is bipartite with parts \(\{1,3,5\}\) and \(\{2,4,6\}\): each of the six cycle edges joins opposite parts, and \(14\) also joins opposite parts. Its bipartite bound is \(2n-4=2\cdot6-4=12-4=8\), and \(7\le8\). Neither bound obstructs planarity.
In this case the graph is planar: draw the cycle \(1,2,3,4,5,6,1\) as the boundary of a convex hexagon and draw edge \(14\) as a diagonal inside it. There is only one diagonal, so it cannot cross another diagonal; it meets the boundary only at its endpoints.
Check: The edge count is seven, and the independent description as six boundary edges plus one diagonal gives the same count. The planar drawing confirms planarity here, but the inequalities alone did not provide that confirmation.
Worked Example: An Isolated Vertex Can Weaken the Test
Let \(G\) have \(V=\{a_1,a_2,a_3,b_1,b_2,b_3,x\}\) and \(E=\{a_i b_j:1\le i\le3,\ 1\le j\le3\}\). Thus \(G\) consists of \(K_{3,3}\) and the isolated vertex \(x\). What do the bounds say?
The order is \(n=3+3+1=7\). The nine pairs \(a_i b_j\) are all edges, so \(m=3\cdot3=9\). The graph is bipartite with parts \(\{a_1,a_2,a_3,x\}\) and \(\{b_1,b_2,b_3\}\); the isolated vertex creates no edge that could violate the partition. The bipartite bound is \(2n-4=2\cdot7-4=14-4=10\), and \(9\le10\). The ordinary bound is \(3n-6=3\cdot7-6=21-6=15\), and \(9\le15\). Neither bound rejects \(G\).
Nevertheless, \(G\) is nonplanar. It contains the subgraph on \(\{a_1,a_2,a_3,b_1,b_2,b_3\}\), which is \(K_{3,3}\), already known to be nonplanar. If \(G\) had a plane embedding, deleting \(x\) would leave a plane embedding of that subgraph, a contradiction. This illustrates why passing the numerical tests is not evidence strong enough to conclude planarity.
Check: The isolated vertex changes the order from \(6\) to \(7\) but adds no edge. Accordingly, the bipartite threshold rises from \(2\cdot6-4=8\) to \(2\cdot7-4=10\), while the edge count remains \(9\). The bound becomes inconclusive even though the graph still contains a nonplanar subgraph.
What a Successful Test Does—and Does Not—Say
A failed inequality is a certificate of nonplanarity: assuming a plane embedding would imply the applicable Euler bound, while the computed edge count contradicts it. The conclusion relies on all hypotheses of the bound. In particular, using \(2n-4\) without first establishing bipartiteness is not a valid test.
A satisfied inequality is different. It says only that the graph has not been ruled out by that count. Other obstructions may remain, as the graph with an isolated vertex illustrates. To prove planarity, one needs a valid plane embedding or another sufficient argument; an edge count below the threshold is not itself such an argument.
Common mistake: applying the bipartite bound to a non-bipartite graph. Let \(T\) be the triangle with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\). It has \(n=3\) and \(m=3\). The bipartite bound would give \(2n-4=2\cdot3-4=6-4=2\), and \(3>2\). It would be wrong to conclude that \(T\) is nonplanar: the hypothesis is missing, since the triangle is not bipartite. In fact, its three edges can be drawn as the boundary of a triangle with no crossings. The ordinary bound is the applicable one here: \(3n-6=3\cdot3-6=9-6=3\), and \(m=3\) satisfies it.
Check Your Understanding
For each question, identify the applicable bound and explain what the comparison does—and does not—establish.
- A simple graph has \(n=8\) vertices and \(m=19\) edges. Does the ordinary planar edge bound rule out planarity?
- A bipartite graph has \(n=9\) vertices and \(m=15\) edges. Does the bipartite bound rule out planarity?
- Why is it invalid to apply \(m\le2n-4\) to a graph before establishing that it is bipartite?
- A graph and its isolated-vertex extension both pass the ordinary bound. Does that prove either graph is planar? Explain.
- State why a violation of an applicable Euler bound proves nonplanarity, while satisfying it does not prove planarity.