From Planar Edges to a Low-Degree Vertex
A coloring argument often begins by removing a vertex and coloring the remaining graph. This is particularly useful when the removed vertex has few neighbors: after coloring the rest, one can try to assign it a color not used by any neighbor. The planar edge bound guarantees that this reduction is always available with at most five neighbors. The point is not that every planar graph has a vertex of degree at most four; some have all vertices of degree five. That sharp boundary is important in coloring arguments.
Throughout, graphs are finite and simple: they have no loops or multiple edges. A graph is planar if it can be drawn in the plane with edges meeting only at common endpoints. Its order is \(n=|V|\), its size is \(m=|E|\), and \(\deg(v)\) is the number of edges incident with vertex \(v\).
The bound applies whether or not \(G\) is connected. We first prove it for a connected graph, where Euler’s formula supplies the key count, and then account for disconnected graphs.
Proving the Planar Edge Bound
For a connected plane graph, let \(F\) be its set of faces and \(f=|F|\). We use Euler’s formula \(n-m+f=2\), the standard result for connected plane graphs. A face boundary is counted as a walk, so a bridge may occur twice on the same boundary and its two occurrences are both counted in the boundary length.
Why each face has boundary length at least three. A boundary of length one would require a loop, which simplicity forbids. A boundary of length two would have to traverse the same edge in opposite directions, since multiple edges are forbidden. For the boundary walk to reverse direction at an endpoint, that endpoint must have degree one; thus both endpoints would have degree one. In a connected graph this would make the entire graph a single edge, contrary to \(n\ge3\). Therefore every face boundary has length at least three.
The equality on the right holds because every edge has two sides, and each side is counted once among the face boundaries. Combining \(3f\le2m\) with Euler’s formula gives the bound:
For a disconnected graph, apply this connected bound to its components, with small components handled directly. If a component has one vertex, it has zero edges; if it has two vertices, it has at most one edge; and if it has \(n_i\ge3\) vertices, it has at most \(3n_i-6\) edges. Each component therefore has at most \(3n_i-3\) edges. If there are \(c\ge2\) components, summing gives \(m\le3n-3c\le3n-6\). If there is one component, the connected bound already applies. This proves the lemma in all cases.
Proof. If \(m=3n-6\), Euler’s formula gives \(f=2-n+m=2n-4\), so \(3f=6n-12=2m\). The sum of the face-boundary lengths is \(2m\), and each of the \(f\) lengths is at least three. Since their sum is exactly \(3f\), every one of them must equal three. Conversely, if every face boundary has length three, then \(2m=3f\). Substituting \(f=2-n+m\) gives \(2m=3(2-n+m)\), hence \(m=3n-6\). \(\square\)
A connected plane graph in this equality case is often called a triangulation: all its faces are triangles. The equality is impossible for a disconnected simple planar graph with \(n\ge3\). To see the strictness, if it has at least three components the bound \(m\le3n-3c\) is already strict. With two components, if both have at least three vertices, their component bounds sum to at most \(3n-12\). If one has one vertex and the other at least three, the sum is at most \(3(n-1)-6=3n-9\). If one has two vertices and the other at least three, it is at most \(1+3(n-2)-6=3n-11\). When the component sizes are one and two, the total is at most one edge, also strictly less than \(3n-6=3\). Thus equality requires connectedness as well as triangular face boundaries.
The Low-Degree Vertex Lemma
Proof. If \(n=1\), the sole vertex has degree zero. If \(n=2\), simplicity gives maximum degree at most one. Now suppose \(n\ge3\). The handshake lemma states that the sum of the vertex degrees is \(2m\), since each edge contributes one to the degree of each endpoint. The planar edge bound therefore gives
If every vertex had degree at least six, the sum would be at least \(6n\), contradicting this strict inequality. Thus some vertex has degree at most five. \(\square\)
The strict inequality is useful, but the conclusion must be read with care: it forces a degree below six, not necessarily below five. Since degrees are integers, “below six” means at most five. The bound is sharp; the next example exhibits a planar graph in which every vertex has degree exactly five.
Worked Example: Equality in the Planar Edge Bound
Let \(G\) be the complete graph \(K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). It is planar: draw a triangle on \(1,2,3\) and place \(4\) inside it, joining \(4\) to all three corners.
Here \(n=4\) and \(m=6\). Substituting in the bound gives \(3n-6=3\cdot4-6=6\), so \(m=3n-6\). Each vertex is incident with the other three vertices, hence the four degrees are \(3,3,3,3\). Their sum is \(12\), and the handshake check gives \(2m=2\cdot6=12\).
Check: Euler’s formula gives \(f=2-n+m=2-4+6=4\). The plane drawing has four triangular faces, consistent with the equality characterization and with the sum of face lengths \(4\cdot3=12=2m\).
Worked Example: Applying the Bound to a Wheel
Let \(V=\{c,1,2,3,4,5\}\) and \(E=\{c1,c2,c3,c4,c5,12,23,34,45,51\}\). This is a planar graph: draw the cycle \(1,2,3,4,5,1\) as a pentagon and join its vertices to the interior vertex \(c\).
There are \(n=6\) vertices and \(m=10\) edges. The edge bound gives \(m\le3n-6=3\cdot6-6=12\), which holds because \(10\le12\). The center \(c\) has degree \(5\). Each of \(1,2,3,4,5\) has two neighbors on the cycle and the neighbor \(c\), so each has degree \(3\). Thus the degree sum is \(5+5\cdot3=20\), agreeing with \(2m=2\cdot10=20\).
Check: The minimum degree is \(3\), so the low-degree conclusion holds directly. The graph does not attain the edge bound: \(12-10=2\) edges short. Its embedding has one pentagonal outer face and five triangular inner faces; their total boundary length is \(5+5\cdot3=20=2m\).
When Degree Five Is Necessary
The edge bound also gives a useful threshold for graphs whose vertices all have degree at least five. If \(\deg(v)\ge5\) for every vertex, then \(2m=\sum_v\deg(v)\ge5n\). Combining this with \(2m\le6n-12\) shows that \(5n\le6n-12\), so \(n\ge12\). Thus a simple planar graph with minimum degree at least five must have at least twelve vertices.
Worked Example: The Icosahedral Graph Has All Degrees Five
Define vertices \(t,b,u_0,u_1,u_2,u_3,u_4,v_0,v_1,v_2,v_3,v_4\), with indices on \(u_i,v_i\) read modulo \(5\). Take the following edge set: \(tu_i\) for every \(i\); \(bv_i\) for every \(i\); \(u_iu_{i+1}\) for every \(i\); \(v_iv_{i+1}\) for every \(i\); and \(u_iv_i\) and \(u_iv_{i-1}\) for every \(i\). This is the icosahedral graph. Its planar embedding has the five triangles \(tu_iu_{i+1}\), the five triangles \(bv_iv_{i+1}\), and the ten triangles \(u_iu_{i+1}v_i\) and \(u_iv_{i-1}v_i\). These form the triangular faces of an embedding on the sphere, or equivalently in the plane with one face chosen as the outer face.
There are \(n=12\) vertices. The five edge families have sizes \(5,5,5,5,10\), respectively, so \(m=5+5+5+5+10=30\). Each of \(t\) and \(b\) has degree \(5\). Each \(u_i\) has neighbors \(t,u_{i-1},u_{i+1},v_i,v_{i-1}\), giving degree \(5\); each \(v_i\) has neighbors \(b,v_{i-1},v_{i+1},u_i,u_{i+1}\), also giving degree \(5\). Thus the degree sum is \(12\cdot5=60\), and independently \(2m=2\cdot30=60\).
Check: The planar bound is \(3n-6=3\cdot12-6=30=m\), so this graph attains equality. Its twenty triangular faces have total boundary length \(20\cdot3=60=2m\), as required. In particular, there is no vertex of degree at most four. The lemma’s bound of five cannot be improved to four for all simple planar graphs.
More generally, if every vertex has degree exactly five, then \(2m=5n\). Equality in this equation combined with the planar bound gives \(5n\le6n-12\), hence \(n\ge12\). At \(n=12\), it forces \(m=30=3n-6\), so the graph is a triangulation. The icosahedral graph shows that this limiting situation does occur. These facts identify the sharp degree boundary without claiming that all graphs with degree five have the same structure.
Why the Lemma Matters for Coloring
In a proper vertex coloring, adjacent vertices must receive different colors. If a vertex \(v\) has at most four neighbors, then after coloring \(G-v\) with five colors, at most four colors are forbidden at \(v\). At least one of the five colors remains available. This is the elementary reduction behind the coloring use of the low-degree lemma: remove a low-degree vertex, color the smaller graph, and then restore the vertex.
When the available vertex has degree five, its five neighbors could use all five colors. The same immediate choice is then unavailable. This is why “at most five” is a crucial starting point rather than, by itself, a complete coloring argument. The additional recoloring method for this case is treated separately in the material on Kempe chains and color-swapping.
Common mistake. From an average degree strictly below six, it is incorrect to conclude that some vertex has degree at most four. The icosahedral graph has average degree \(60/12=5\) and every vertex has degree five. The valid inference is that not all degrees can be at least six, so some integer degree is at most five. For a simple planar graph, the edge bound gives average degree at most \((6n-12)/n=6-12/n\), which is strictly less than six for every \(n\ge3\).
Check Your Understanding
Use the edge bound and degree counting in each question. When invoking the bound, check that its order hypothesis is satisfied.
- For a connected simple planar graph with \(n=7\), what is the largest edge count allowed by the planar edge bound?
- Explain why a simple planar graph with \(n=10\) cannot have every vertex of degree at least five.
- For a connected simple planar graph with \(n\ge3\), prove that if every face is triangular, then \(m=3n-6\).
- Why does a vertex of degree at most four allow an immediate extension of a five-coloring of the graph with that vertex deleted?
- Give the vertex set and edge count of the icosahedral graph example, and explain why it shows that the low-degree bound cannot be reduced to four.