Regularity as a Degree Condition
A graph can have many vertices and edges yet still be tightly constrained if every vertex has the same degree. This common degree condition gives an immediate relationship between the order of a graph, its size, and the degree of each vertex. It also provides quick tests for proposed examples: some combinations of order and degree are impossible before any edge list is considered.
Throughout, graphs are finite and simple: they have no loops or multiple edges. The order of \(G\) is \(n=|V(G)|\), and its size is \(m=|E(G)|\). The degree \(\deg(v)\) is the number of edges incident with vertex \(v\).
We require the graph to be nonempty in this definition, so its regularity degree is unambiguous. A \(0\)-regular graph has no edges: every vertex has degree zero. A \(1\)-regular graph has exactly one edge incident with each vertex. Regularity concerns all vertices; having only some vertices of the same degree does not make the graph regular.
Two Necessary Constraints
The handshake lemma states that the sum of the vertex degrees is twice the number of edges. Each edge contributes one to the degree of each of its two endpoints, and therefore contributes two to the total degree sum. In a \(d\)-regular graph, the same sum is also \(d\) added once for each of the \(n\) vertices.
Proof. Degrees are counts of incident edges, so \(d\ge 0\). Since the graph is simple, a vertex can be adjacent to at most the other \(n-1\) vertices, giving \(d\le n-1\). By the handshake lemma, the sum of the degrees equals \(2m\). Regularity makes that sum \(nd\), so \(nd=2m\) and \(m=nd/2\). Since \(m\) is an integer, \(nd\) must be even. If \(n\) and \(d\) were both odd, their product \(nd\) would be odd, contradicting this condition. \(\square\)
The upper bound comes specifically from simplicity. If loops or multiple edges were allowed, a vertex could have degree greater than \(n-1\). Here it cannot. Another way to see the bound is that a simple graph on \(n\) vertices has at most one edge for each pair of distinct vertices, and there are \(n(n-1)/2\) such pairs. Thus \(m\le n(n-1)/2\); for a regular graph, \(nd/2\le n(n-1)/2\), which also gives \(d\le n-1\) because \(n\ge1\).
These are necessary conditions: every simple \(d\)-regular graph must satisfy them. They are useful for rejecting impossible proposals, but they do not check whether a particular edge list actually gives every vertex degree \(d\). For that, count the degrees in the graph that was proposed.
Worked Example: An Odd Degree on an Odd Number of Vertices
Could a simple \(3\)-regular graph have \(5\) vertices? The proposed parameters are \(n=5\) and \(d=3\). The degree bound passes because \(3\le 5-1=4\). The handshake condition does not: \(nd=5\cdot3=15\), which is odd.
If such a graph existed, its edge count would have to be \(m=nd/2=15/2\), which is not an integer. An edge count must be a whole number, so no such graph exists.
Check: the contradiction can also be read from the degree sum. Five vertices of degree \(3\) would give total degree \(5\cdot3=15\), but each edge contributes two to the total, so the total must be even. The proposed parameters fail the same condition both ways.
Boundary Cases and Useful Consequences
The degree bounds also explain two simple cases. If \(d=0\), the formula gives \(m=n\cdot0/2=0\), so every \(0\)-regular graph is edgeless. Conversely, an edgeless graph with at least one vertex is \(0\)-regular by the definition.
If \(d=n-1\), each vertex must be adjacent to every other vertex. In a simple graph, that means every possible edge is present, so the graph is the complete graph \(K_n\). Its edge count is \(n(n-1)/2\), matching the regular edge-count formula \(nd/2=n(n-1)/2\). For \(n=1\), this boundary case gives \(d=0\): the single-vertex graph is \(0\)-regular.
Proof. For a \(1\)-regular graph, the edge-count formula gives \(m=n\cdot1/2=n/2\). Since \(m\) is an integer, \(n/2\) is an integer, so \(n\) is even. \(\square\)
This conclusion is a constraint, not a way to verify an edge list: an even number of vertices is required, but one must still check the degrees in any particular proposed graph. More generally, if \(n\) is odd, the parity condition forces \(d\) to be even. If \(d\) is odd, it forces \(n\) to be even.
Worked Example: A \(2\)-Regular Graph on Five Vertices
Consider the graph \(G=(V,E)\) with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). This is a cycle on five vertices, but we can check regularity directly from the edge list.
Vertex \(1\) is incident with \(12\) and \(51\), so \(\deg(1)=2\). Vertex \(2\) is incident with \(12\) and \(23\), so \(\deg(2)=2\). Vertex \(3\) is incident with \(23\) and \(34\), so \(\deg(3)=2\). Vertex \(4\) is incident with \(34\) and \(45\), so \(\deg(4)=2\). Vertex \(5\) is incident with \(45\) and \(51\), so \(\deg(5)=2\). Thus every vertex has degree \(2\), and \(G\) is \(2\)-regular.
The formula predicts \(m=nd/2=(5\cdot2)/2=10/2=5\), agreeing with the five listed edges. Independently, the degree sum is \(2+2+2+2+2=10\), and the handshake lemma gives \(m=10/2=5\). This example also shows why odd order alone does not rule out regularity: the parity obstruction occurs when both \(n\) and \(d\) are odd, not whenever \(n\) is odd.
Check the Edge List, Not Just the Parameters
A regularity claim has two parts: the graph must have the stated order and size, and each vertex must have the stated degree. The numerical formula checks whether the claimed order, degree, and edge count agree. It does not replace counting the incidences in a specified graph.
Worked Example: Verifying a Proposed \(2\)-Regular Graph
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\). We check whether this edge list defines a \(2\)-regular graph.
From the listed edges, vertex \(1\) is incident with \(12,61\); vertex \(2\) with \(12,23\); vertex \(3\) with \(23,34\); vertex \(4\) with \(34,45\); vertex \(5\) with \(45,56\); and vertex \(6\) with \(56,61\). Every vertex therefore has degree \(2\), so the graph is indeed \(2\)-regular.
Here \(n=6\), \(d=2\), and the list contains \(m=6\) edges. The formula gives \(nd/2=(6\cdot2)/2=12/2=6\). As a second check, the degree sum is \(6\cdot2=12\), and half of it is \(12/2=6\) edges. Both checks agree with the edge list.
Worked Example: Verifying a \(3\)-Regular Graph
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). There are six listed edges. Vertex \(1\) is incident with \(12,13,14\); vertex \(2\) with \(12,23,24\); vertex \(3\) with \(13,23,34\); and vertex \(4\) with \(14,24,34\). Each vertex has degree \(3\), so \(G\) is \(3\)-regular.
The numerical constraints also check out: \(d=3\le n-1=3\), and \(nd=4\cdot3=12\) is even. The predicted edge count is \(m=12/2=6\), equal to the six edges in the list. Independently, the degree sum is \(3+3+3+3=12\), and the handshake lemma gives \(12/2=6\) edges. This graph is \(K_4\), since all six pairs of distinct vertices appear in \(E\).
Common Mistake: Stopping After the Parity Test
A common error is to treat the handshake test as if it verified the graph itself. Suppose someone claims the edge list \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\) is \(2\)-regular. The numerical parameters pass the basic tests: \(d=2\le 4-1=3\), \(nd=4\cdot2=8\) is even, and the required edge count is \(m=8/2=4\). But the list contains only three edges. Its degrees are \(\deg(1)=1\), \(\deg(2)=2\), \(\deg(3)=2\), and \(\deg(4)=1\). Therefore the listed graph is not \(2\)-regular.
The correction is to separate the questions. First, use the bounds, parity, and edge-count formula to see whether the numerical proposal is ruled out. Then, if an actual edge list is given, count the incident edges at every vertex. A numerical test that does not rule out a proposal is not a substitute for this degree check.
Another frequent error is to divide \(nd\) by two incorrectly or to overlook why it must be even. Keep the sequence explicit: the total degree is \(nd\); each edge contributes two; hence \(2m=nd\), so \(m=nd/2\). For example, with \(n=5\) and \(d=3\), \(nd=5\cdot3=15\), and \(15/2\) is not an integer. That failure is exactly the obstruction.
Check Your Understanding
For each question, distinguish the numerical constraints from checking a specified graph.
- Can a simple \(4\)-regular graph have \(7\) vertices? Check both the degree bound and the parity condition.
- A simple graph has \(9\) vertices and is claimed to be \(3\)-regular. What edge count would the formula require, and which constraint rules it out?
- Explain why every nonempty \(0\)-regular graph has no edges.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\), compute each vertex degree and decide whether the graph is regular.
- Why does passing \(d\le n-1\) and \(nd\) even not verify that a proposed edge list is \(d\)-regular?