Small-Order Exceptions to Planar Edge Bounds

Why the Order Condition Matters

The simple planar edge bound is often written \(m\le 3n-6\), where \(n\) is the number of vertices and \(m\) the number of edges. Its order condition is essential: the bound applies to simple planar graphs with at least three vertices. At orders one and two, the formula gives incorrect limits, even though the graphs themselves are uncomplicated. The correct limits follow directly from simplicity: a one-vertex graph has no edges, while a two-vertex graph has at most one.

This distinction is useful whenever an edge bound is applied to a graph whose order is small, or to a graph obtained by deleting vertices. A formula proved under a hypothesis cannot automatically be used after that hypothesis stops holding. We will identify exactly what the small graphs permit, verify that the limits are attained by planar examples, and then state the bound with its proper range.

Definitions and a Basic Counting Fact

Throughout, graphs are finite and simple. Thus an edge joins two distinct vertices, and at most one edge joins any given pair of vertices. A graph \(G=(V,E)\) has order \(n=|V|\) and size \(m=|E|\). It is planar if it can be drawn in the plane with no two edges crossing except at a common endpoint.

The earlier material on Euler’s formula established this bound for the stated range of orders. The present issue is not to rederive it, but to determine what is true when \(n=1\) or \(n=2\). A separate elementary restriction applies to every simple graph, whether planar or not: every edge must use a different unordered pair of distinct vertices. There are \(n(n-1)/2\) such pairs, so

Proof. Each edge \(uv\) corresponds to the unordered pair \(\{u,v\}\) of its endpoints. Since the graph has no loops, \(u\ne v\); since it has no multiple edges, no two edges correspond to the same pair. The number of unordered pairs of distinct vertices is \(\binom{n}{2}\): there are \(n(n-1)\) ordered pairs \((u,v)\) with \(u\ne v\), and each unordered pair is counted in the two orders \((u,v)\) and \((v,u)\). Therefore \(m\le n(n-1)/2\). \(\square\)

For small orders, this pair count is already the decisive restriction. It also explains why there is no need to use a face count to determine the exact limits: the possible edge sets are completely controlled by the available endpoint pairs.

The Exact Limits at Orders One and Two

Proof. If \(n=1\), the pair-count bound gives \(m\le 1(1-1)/2=0\). Since the size \(m\) is a nonnegative integer, \(m=0\). The graph consisting of one vertex and no edges is planar, so the limit is attained.

If \(n=2\), the pair-count bound gives \(m\le 2(2-1)/2=1\). This limit is attained by the graph with two vertices joined by one edge: it can be drawn as a single line segment, so it is planar. Thus the maximum size is exactly \(1\). \(\square\)

These values are exact maxima, not just upper bounds. For order one, there is no pair of distinct vertices to serve as the endpoints of an edge. For order two, there is exactly one such pair, and simplicity allows at most one edge on it. Planarity adds no further restriction at either order because the examples attaining the limits have crossing-free drawings.

Stating the Bound Correctly

The edge limits can be collected into a single statement. The small-order cases come from the pair count proved above. For \(n\ge3\), the simple planar edge bound from the earlier material applies. The result is the following piecewise upper bound.

Proof. When \(n=1\), the pair-count bound gives \(m\le1(1-1)/2=0\). When \(n=2\), it gives \(m\le2(2-1)/2=1\). When \(n\ge3\), all hypotheses of the simple planar edge bound hold: the graph is simple and planar, and its order is at least three. Hence \(m\le3n-6\). These cases cover every integer \(n\ge1\), proving the stated bound. \(\square\)

If a graph has no vertices, then \(n=0\) and \(m=0\). The corollary deliberately starts at \(n=1\), so it makes no claim about order zero. In particular, substituting \(n=0\) into \(3n-6\) is not a valid way to obtain an edge bound for the empty graph.

For a quick check of the transition to the usual range, take the triangle with \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\). It is planar: draw the three vertices as the corners of a triangle and its edges as the sides. Here \(n=3\) and \(m=3\), while \(3n-6=3(3)-6=9-6=3\). The pair count also gives \(\binom{3}{2}=3(3-1)/2=3\). Thus both calculations agree for this particular graph at order three; this check does not replace the general planar bound.

Why These Exceptions Matter

Face-count arguments require care at small orders. The proof of the planar edge bound uses information about a plane embedding, including the way edge-sides contribute to face-boundary lengths. Those arguments are carried out with the order restriction in place. At orders one and two, the direct count of possible endpoint pairs is simpler and gives the exact answer without any assumptions about facial boundaries.

A common mistake is to remember \(m\le3n-6\) but omit its hypothesis. For the two-vertex graph \(V=\{u,v\}\), \(E=\{uv\}\), substituting gives \(m=1\) and \(3n-6=3(2)-6=0\). Claiming \(1\le0\) is an incorrect application of the formula. The correction is to check the order first: since \(n=2\), use the small-order limit \(m\le1\), obtained from the single possible endpoint pair.

Another tempting but incomplete argument is to test only an edgeless graph of order two. Its size is \(0\), and \(3(2)-6=0\), so it happens to satisfy the expression. But a bound is a statement about all graphs in its stated class. The one-edge graph has size \(1\), and therefore disproves the claimed order-two bound. Testing a single graph can verify an example; it cannot establish a universal inequality.

For practical use, identify the graph class and its order before choosing an edge bound. Simplicity supplies the pair-count bound at every order. Planarity supplies the stronger expression \(3n-6\) only once \(n\ge3\). Keeping these roles distinct prevents small exceptions from being mistaken for counterexamples to a correctly stated theorem.