Edge Counts in Regular Graphs

Regularity Determines the Edge Count

In a regular graph, every vertex has the same degree. This uniformity makes the handshake lemma especially direct: the total degree is obtained by multiplying one degree by the number of vertices. Since each edge contributes to the degree of both its endpoints, that total also counts every edge twice. Equating these counts gives the edge count and an immediate restriction on which parameters are possible.

Throughout, graphs are finite and simple: they have no loops or multiple edges. Write $n=|V(G)|$ for the order of $G$ and $m=|E(G)|$ for its size. We take $n\ge 1$, so the degree of a regular graph is determined by its vertices.

Definition: A graph $G$ is $d$-regular if every vertex $v\in V(G)$ has degree $\deg(v)=d$. Here $d$ is a nonnegative integer. In a simple graph of order $n$, necessarily $0\le d\le n-1$: a vertex has at most the other $n-1$ vertices as neighbors.

The edge-count formula follows from the handshake lemma, which says that the sum of all vertex degrees equals twice the number of edges. Indeed, each edge $uv$ contributes one to $\deg(u)$ and one to $\deg(v)$, hence contributes two to the degree sum. In a $d$-regular graph the same sum is $d$ added once for each of the $n$ vertices.

Theorem: If a finite simple graph $G$ is $d$-regular and has order $n$, then $$ |E(G)|=m=\frac{nd}{2}. $$

Proof. Because every one of the $n$ vertices has degree $d$, the sum of the degrees is $nd$. By counting incidences between vertices and edges, each of the $m$ edges is counted once at each of its two endpoints, so the same degree sum is $2m$. Thus $nd=2m$, and dividing by $2$ gives $m=nd/2$. $\square$

The Parity Condition

The formula has an arithmetic consequence. The number of edges must be an integer, so the product $nd$ must be even. Equivalently, an odd number of vertices cannot all have the same odd degree. This is a necessary condition: if $nd$ is odd, no such graph can exist.

Corollary: If a finite simple $d$-regular graph has order $n$, then $nd$ is even. In particular, if $n$ is odd, then $d$ must be even.

Proof. By the theorem, $nd=2m$. Since $m$ is an integer, $2m$ is even, so $nd$ is even. If $n$ is odd and $d$ were odd, their product would be odd, contradicting this conclusion. Therefore $d$ is even whenever $n$ is odd. $\square$

There is also a useful converse at the level of arithmetic: $nd$ is even exactly when $nd/2$ is an integer. But this only says that the proposed edge count is an integer. It does not prove that a graph with those parameters exists. The simple-graph bound $d\le n-1$ is another necessary test, and even passing both tests is not itself a construction.

Applying the Formula

Worked Example: Counting Edges in a 3-Regular Graph

Let $G=(V,E)$ be defined by $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,34,45,56,61,14,25,36\}$. First verify regularity, then check the edge-count formula.

The neighbors of $1$ are $2,6,4$, so $\deg(1)=3$. The neighbors of $2$ are $1,3,5$, so $\deg(2)=3$. The neighbors of $3$ are $2,4,6$, so $\deg(3)=3$. The neighbors of $4$ are $3,5,1$, so $\deg(4)=3$. The neighbors of $5$ are $4,6,2$, so $\deg(5)=3$. The neighbors of $6$ are $5,1,3$, so $\deg(6)=3$. Thus $G$ is 3-regular.

Here $n=6$ and $d=3$, so the formula gives $m=nd/2=(6\cdot3)/2=18/2=9$. Directly, the listed edge set has nine distinct edges. As a further check, the sum of the six degrees is $3+3+3+3+3+3=18$, and dividing by two gives $18/2=9$ edges.

Worked Example: A 2-Regular Graph on Five Vertices

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. Each vertex has two neighbors: $1$ has $2,5$; $2$ has $1,3$; $3$ has $2,4$; $4$ has $3,5$; and $5$ has $4,1$. Hence $G$ is 2-regular.

With $n=5$ and $d=2$, the formula gives $m=nd/2=(5\cdot2)/2=10/2=5$. The edge set contains five distinct edges, confirming the result. The parity test also passes: $nd=5\cdot2=10$, which is even. This example illustrates the corollary: an odd order is compatible with regularity when the common degree is even.

Worked Example: Parity Rules Out a Proposed Degree

Could a simple graph on $V=\{1,2,3,4,5\}$ be 3-regular? Suppose such a graph existed. Its order would be $n=5$ and its common degree $d=3$, so the degree sum would be $nd=5\cdot3=15$. The handshake lemma requires this sum to equal twice the number of edges, and therefore to be even. But $15$ is odd, a contradiction. Thus no such graph exists.

The edge-count formula gives the same contradiction in another form: $m=nd/2=(5\cdot3)/2=15/2$, which is not an integer. The two checks agree because the formula is exactly the handshake count solved for $m$.

Worked Example: Passing Parity Is Not Enough

Consider the proposed parameters $n=3$ and $d=4$. Their product is $nd=3\cdot4=12$, which is even, and the formula would give $m=12/2=6$. So parity does not rule out these parameters. However, in a simple graph on three vertices, any vertex can be adjacent to at most the other two vertices. Therefore every degree is at most $3-1=2$, and degree $4$ is impossible. The proposed parameters fail the simple-graph degree bound.

For comparison, there are exactly three possible pairs of distinct vertices on a three-vertex set: $12,13,23$. A simple graph can use at most these three edges, so it cannot have the six edges predicted by the proposed parameters. This direct count confirms the degree-bound conclusion. The parity test is necessary, not sufficient.

Using the Tests Carefully

For proposed parameters $n$ and $d$ for a simple regular graph, apply the basic tests in a fixed order:

Check the range.
Require $n\ge1$ and $0\le d\le n-1$. The degree is nonnegative, and a vertex cannot have more than the other $n-1$ vertices as neighbors.

Check parity.
Compute $nd$. If it is odd, no such graph exists, because the total degree must equal twice an integer edge count.

Compute the forced edge count.
If both tests pass, calculate $m=nd/2$. This is the only possible number of edges; the tests alone do not exhibit a graph.

The case $d=0$ fits the formula without any exception. Every vertex then has no incident edges, so $m=0$, and $nd/2=n\cdot0/2=0$. At the other extreme, $d=n-1$ forces every vertex to be adjacent to every other vertex; the formula gives $m=n(n-1)/2$, the number of distinct pairs of vertices. These checks illustrate that the count applies at the ends of the allowed degree range as well as between them.

Common Mistake: Forgetting That Each Edge Is Counted Twice

A common error is to report $nd$ as the number of edges. In the first worked example, this would give $6\cdot3=18$ edges. But $18$ is the sum of the degrees, not the size of the graph: each edge contributes at both endpoints. The correction is to divide by two, giving $18/2=9$ edges, which agrees with the explicitly listed edge set.

The parity conclusion is the same double-counting fact viewed before division. If $nd$ is odd, it cannot equal $2m$ for any integer $m$, so the proposed regular graph cannot exist. If $nd$ is even, division gives an integer candidate for the edge count, but one must still respect the simple-graph degree bound and, when asking about existence, establish that a graph can actually be formed.

Check Your Understanding

For each question, state which count or condition you use, and show the arithmetic needed to support your answer.

A 4-regular simple graph has 7 vertices. How many edges must it have? Check the parity condition.
Can a simple 3-regular graph have 7 vertices? Explain using the product of its order and degree.
For $n=4$ and $d=4$, does the parity test rule out a regular simple graph? If not, identify the other necessary condition that fails.
Explain why the degree sum $nd$ of a $d$-regular graph is not itself the number of edges.
A graph has order $n\ge1$ and is 0-regular. Use the formula to determine its size.

What You'll Learn