Why Planar Graphs Must Have Low-Degree Vertices
A planar graph cannot have too many edges compared with its number of vertices. This restriction limits its average degree, and an average-degree bound forces at least one vertex to have small degree. The conclusion is useful beyond locating one vertex: after removing that vertex, the remaining graph is still planar, so the argument can be repeated. This gives a systematic way to order the vertices of any simple planar graph.
Throughout, graphs are finite and simple: they have no loops or multiple edges. A graph \(G=(V,E)\) is planar if it can be drawn in the plane with no two edges crossing except at a shared endpoint. A graph obtained by deleting some vertices and their incident edges is a subgraph; in particular, every subgraph of a planar graph is planar. We write \(n=|V|\), \(m=|E|\), and \(\deg(v)\) for the degree of a vertex \(v\).
The condition \(n\ge3\) matters: the bound is not asserted for graphs of order one or two. In the proof below, smaller remaining graphs will be handled directly rather than by applying this bound outside its hypotheses.
The Degree-Sum Identity
Proof. Count incidences consisting of an edge together with one of its endpoints. When the incidences are counted by vertex, vertex \(v\) contributes \(\deg(v)\), so the total is \(\sum_{v\in V}\deg(v)\). When they are counted by edge, each edge has exactly two distinct endpoints, so each edge contributes two incidences. Thus the same total is \(2|E|\). Isolated vertices contribute zero, so the count also applies when they are present. \(\square\)
The average degree is the sum of the degrees divided by the number of vertices, provided \(n>0\). For a simple planar graph with \(n\ge3\), the degree-sum identity and the edge bound give $$ \frac{1}{n}\sum_{v\in V}\deg(v)=\frac{2m}{n}\le\frac{2(3n-6)}{n}=6-\frac{12}{n}<6. $$ The strict inequality follows from \(n\ge3\), which implies \(12/n>0\). The average being below six does not say that every degree is below six. It says that at least one degree is below six; since degrees are integers, that degree is at most five.
The Low-Degree Vertex Theorem
Proof. Let \(G=(V,E)\) be a simple planar graph with \(n=|V|\ge3\). Suppose, for contradiction, that every vertex has degree at least six. Then \(\sum_{v\in V}\deg(v)\ge6n\). But the degree-sum identity and the simple planar edge bound give $$ \sum_{v\in V}\deg(v)=2m\le 2(3n-6)=6n-12<6n, $$ contradicting \(\sum_{v\in V}\deg(v)\ge6n\). Hence some vertex has degree less than six. Since its degree is an integer, it is at most five. \(\square\)
This argument places no connectedness requirement on \(G\). The edge bound applies to the whole graph, and the degree-sum identity counts every component. An isolated vertex, if present, already has degree zero. The theorem also makes no claim that all vertices have degree at most five; the conclusion is about the existence of at least one such vertex.
Worked Example: Equality in the Edge Bound for \(K_4\)
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). This is \(K_4\), which is planar. For example, draw \(1,2,3\) as a triangle, place \(4\) inside it, and join \(4\) to each of \(1,2,3\).
There are \(n=4\) vertices and \(m=6\) edges. The simple planar edge bound gives \(m\le3n-6=3(4)-6=12-6=6\), so equality holds. Each vertex is adjacent to the other three, giving degree sequence \(3,3,3,3\). Thus the degree sum is \(3+3+3+3=12\), while \(2m=2(6)=12\), as required by the degree-sum identity. The minimum degree is \(3\), which is at most five.
Check: the degree calculation counts each of the six listed edges at both endpoints, for \(12\) endpoint incidences in total. The edge-bound calculation also gives \(6\), exactly the listed number of edges.
Worked Example: A Planar Graph Can Have a Vertex of Degree Six
Let \(G=(V,E)\), where \(V=\{c,1,2,3,4,5,6\}\) and \(E=\{c1,c2,c3,c4,c5,c6,12,23,34,45,56,61\}\). This is a wheel: draw the cycle \(1,2,3,4,5,6,1\) as a hexagon and place \(c\) inside it, joined to all six cycle vertices. This gives a plane drawing without crossings.
There are \(n=7\) vertices and \(m=12\) edges: six edges incident with \(c\) and six edges on the cycle. The edge bound gives \(m\le3(7)-6=21-6=15\), which is satisfied. The center has degree \(\deg(c)=6\). Each of the six cycle vertices has two neighbors on the cycle and is also adjacent to \(c\), so each has degree \(3\). Therefore the degree sum is \(6+6(3)=6+18=24\). Independently, \(2m=2(12)=24\).
The average degree is \(24/7<6\), but the maximum degree is \(6\). The theorem is consistent with this: the six cycle vertices have degree \(3\), so in particular at least one vertex has degree at most five. This example shows why the conclusion is about a low-degree vertex, not a bound on every vertex.
Worked Example: A Disconnected Graph with an Isolated Vertex
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,ac,ad,bc,bd,cd\}\). The vertices \(a,b,c,d\) form a \(K_4\), and \(e\) is isolated. This graph is planar: use a plane drawing of \(K_4\) and place \(e\) away from it.
Here \(n=5\) and \(m=6\). The edge bound gives \(m\le3(5)-6=15-6=9\). The degrees of \(a,b,c,d\) are each \(3\), and \(\deg(e)=0\). Thus \(\sum_{v\in V}\deg(v)=3+3+3+3+0=12\), while \(2m=2(6)=12\). The isolated vertex itself has degree at most five, so the theorem holds. This example also illustrates that disconnectedness and isolated vertices cause no exception.
Repeated Removal and Elimination Orderings
The theorem can be applied repeatedly. At each stage, remove a vertex of degree at most five from the graph that remains. Since deleting vertices preserves simplicity and planarity, every remaining graph is still simple and planar. If it has at least three vertices, the theorem supplies a vertex of degree at most five. If it has one or two vertices, every vertex has degree at most one, so a suitable vertex can still be removed. Stop when no vertices remain.
Proof. We construct the ordering by removal. If the graph is empty, the empty ordering satisfies the definition, so suppose it has vertices. While at least three vertices remain, the remaining graph is a simple planar graph, and the Low-Degree Vertex Theorem provides a vertex of degree at most five in that remaining graph. Remove one such vertex and record it next in the ordering. If one or two vertices remain, remove them in either order: in a simple graph on at most two vertices, each vertex has at most one neighbor. Continue until no vertices remain. When \(v_i\) was removed, the vertices still present were exactly \(v_{i+1},\ldots,v_n\). Its neighbors among those vertices were its neighbors in the graph at the time of removal, and there were at most five. Therefore the recorded removal order has the required property. \(\square\)
Keep track of the direction: in the removal order, each vertex has at most five neighbors appearing later, because those are the vertices still present when it is removed. If the order is read backwards, each vertex has at most five neighbors appearing earlier. These are two equivalent ways to describe the same ordering, with the word “earlier” or “later” changing when the order is reversed.
Worked Example: Removing the Leaves of a Star
Let \(G=(V,E)\), where \(V=\{x,a,b,c,d,e,f\}\) and \(E=\{xa,xb,xc,xd,xe,xf\}\). This is the star \(K_{1,6}\), which is planar. The center \(x\) has degree \(6\), and each of \(a,b,c,d,e,f\) has degree \(1\). The edge bound gives \(m=6\le3(7)-6=15\), and the degree sum is \(6+6(1)=12=2(6)\).
Remove the leaves in the order \(a,b,c,d,e,f\), then remove \(x\). The table records the degree of the removed vertex immediately before its removal and the degree of \(x\) immediately afterward.
| Step | Removed vertex | Degree at removal | Degree of \(x\) afterward |
|---|---|---|---|
| 1 | \(a\) | 1 | 5 |
| 2 | \(b\) | 1 | 4 |
| 3 | \(c\) | 1 | 3 |
| 4 | \(d\) | 1 | 2 |
| 5 | \(e\) | 1 | 1 |
| 6 | \(f\) | 1 | 0 |
| 7 | \(x\) | 0 | 0 |
For this removal order, each leaf has just one neighbor appearing later, namely \(x\), and \(x\) has no neighbors appearing later. Thus every vertex has at most five neighbors later. In the reversed order \(x,f,e,d,c,b,a\), each vertex has at most five neighbors earlier: \(x\) has none earlier, and each leaf has only \(x\) earlier. The degree and edge-count checks agree: the degrees sum to \(12\), and the six listed edges contribute \(2(6)=12\) incidences.
Common Pitfall and Why the Result Matters
Confusing an average bound with a maximum bound. From \(2m/n<6\), it is incorrect to conclude that every vertex has degree at most five. In the wheel example, \(n=7\), \(m=12\), and the average degree is \(24/7<6\), yet the center has degree \(6\). The valid conclusion is that not all vertices can have degree at least six: otherwise their degree sum would be at least \(6n\), contradicting \(2m\le6n-12\). Since degrees are integers, at least one degree is at most five.
Reversing the ordering without reversing “earlier” and “later.” In the star example, the removal order \(a,b,c,d,e,f,x\) has at most five neighbors later for each vertex. In the reversed order, the center \(x\) appears first and has six neighbors later, so the statement “at most five neighbors later” is no longer true. What is true in the reversed order is that each vertex has at most five neighbors earlier.
The main point is that the planar edge bound controls not just the total number of edges, but also the degree structure. A graph may contain high-degree vertices, yet it must contain a vertex of degree at most five. Repeating this fact produces an elimination ordering, which is useful when analyzing planar graphs inductively: one can first study a smaller graph, then account for the removed vertex and its at-most-five remaining neighbors.
Check Your Understanding
Use the edge bound, the degree-sum identity, and the removal-order definition to answer these questions.
- For a simple planar graph with \(n=8\), what upper bound does \(m\le3n-6\) give for \(m\), and what upper bound does it give for the average degree?
- Why does a degree sum less than \(6n\) imply that some vertex has degree at most five, rather than merely that some degree is less than six?
- Can the Low-Degree Vertex Theorem be applied to a disconnected simple planar graph with an isolated vertex? Explain which hypothesis matters.
- In a removal ordering, which vertices count as “later” neighbors of the vertex being removed?
- If a valid removal ordering is reversed, should the bound of five refer to earlier or later neighbors? Explain.