Counting Edges from Degree Data

From Degrees to an Edge Count

A degree list records how many edges meet each vertex. Although it does not usually tell us which vertices are joined, it does determine the number of edges whenever the list comes from a finite undirected graph. The key is to count the same incidences in two ways: once by vertices and once by edges.

Throughout, graphs are finite and simple: there are no loops or multiple edges. For a graph $G=(V,E)$, the degree $\deg(v)$ is the number of edges incident with $v$, and the edge count is $m=|E|$. A degree list for $G$ has one entry for each vertex; its order can follow a chosen vertex labeling or be sorted into non-increasing order. Sorting changes the order of the entries, not their sum.

Recall: Handshake lemma. For every finite undirected graph $G=(V,E)$, the sum of the vertex degrees is twice the number of edges: $$ \sum_{v\in V}\deg(v)=2|E|. $$ Each edge has two endpoints and therefore contributes two incidences to the degree sum. The handshake lemma was established by counting these incidences in the earlier material on the handshake lemma.

If the degree list is $d_1,d_2,\dots,d_n$, and it is realized by a graph, then the number of edges is necessarily

m=\frac{d_1+d_2+\cdots+d_n}{2}.

The assumption that the list is realized matters: this formula calculates the edge count of a graph with those degrees, but it does not prove that such a graph exists. In particular, it gives a necessary parity check, not a complete realization test.

The Edge-Count Rule and Its Consequences

Proposition: If a finite undirected graph has degree list $d_1,\dots,d_n$, then its number of edges is uniquely determined by that list and equals $\frac12\sum_{i=1}^n d_i$.

Proof. Let $G$ be any graph realizing the list. By the handshake lemma, $\sum_{i=1}^n d_i=\sum_{v\in V(G)}\deg(v)=2|E(G)|$. Dividing both sides by $2$ gives $|E(G)|=\frac12\sum_{i=1}^n d_i$. The right-hand side depends only on the list. Therefore any graph realizing that same list has the same number of edges. $\square$

An equivalent practical rule applies when the data are given as degree frequencies rather than as a list. If $n_j$ vertices have degree $j$, then those vertices contribute $j n_j$ to the total degree sum. Adding the contributions of every degree class gives the edge count.

Proposition: If $n_j$ vertices have degree $j$, for each degree $j$ present, then any graph with these degree frequencies has $m=\frac12\sum_j jn_j$ edges.

Proof. Each of the $n_j$ vertices of degree $j$ contributes $j$ to the degree sum, so that degree class contributes $jn_j$. Summing over the degree classes gives $\sum_j jn_j=\sum_{v\in V}\deg(v)$. The handshake lemma makes this sum $2m$, and division by $2$ gives the stated formula. $\square$

Because an edge count is an integer, the total degree sum of any realizable list must be even. Thus an odd sum rules out a realization immediately. The reverse implication does not hold in general: an even sum is one necessary check, but more information may be needed to establish that a graph exists.

Worked Example: Finding the Edge Count from a Labeled List

Suppose a simple undirected graph on $V=\{1,2,3,4,5\}$ has degree list $(2,3,2,2,1)$, in that vertex order. Find its number of edges. To verify that the data are realizable, consider the explicit graph with $E=\{12,13,23,24,45\}$.

First add the listed degrees: $2+3+2+2+1=10$. Therefore the edge-count formula gives $m=10/2=5$.

Now check the proposed realization. Vertex $1$ is incident with $12,13$, so its degree is $2$. Vertex $2$ is incident with $12,23,24$, so its degree is $3$. Vertex $3$ is incident with $13,23$, so its degree is $2$. Vertex $4$ is incident with $24,45$, so its degree is $2$. Vertex $5$ is incident with $45$, so its degree is $1$.

Check: the edge set contains $12,13,23,24,45$, which is $5$ edges. Its degree sum, recomputed from the incidences, is $2+3+2+2+1=10=2\cdot5$, as required.

Worked Example: Counting from Degree Frequencies

Consider a simple undirected graph on $V=\{a,b,c,d,e,f,g,h\}$ whose degree data say that three vertices have degree $3$, two have degree $2$, and three have degree $1$. For a realization, take $E=\{ab,ac,bc,ad,be,cf,dg,eh\}$.

The three degree-$3$ vertices contribute $3\cdot3=9$ to the degree sum. The two degree-$2$ vertices contribute $2\cdot2=4$, and the three degree-$1$ vertices contribute $1\cdot3=3$. Thus the total is $9+4+3=16$, so the edge count is $m=16/2=8$.

For the explicit graph, $a$ is incident with $ab,ac,ad$; $b$ with $ab,bc,be$; and $c$ with $ac,bc,cf$. Each has degree $3$. Vertices $d,e$ have incident edges $ad,dg$ and $be,eh$, respectively, so each has degree $2$. Vertices $f,g,h$ each have degree $1$, from $cf,dg,eh$, respectively.

Check: the displayed edge set has eight entries. Independently, its degree sum is $3+3+3+2+2+1+1+1=16$, and $16/2=8$.

Using the Degree Sum to Detect Inconsistency

Proposition: If a finite undirected graph realizes a degree list, the sum of the entries must be even. Consequently, a degree list with odd sum has no realization.

Proof. Suppose a graph realizes the list and has $m$ edges. The handshake lemma says that the sum of its degrees is $2m$, which is even because $m$ is an integer. Therefore any list with odd sum cannot be the degree list of such a graph. $\square$

This test can reject data without constructing or searching for a graph. But passing it only means the test has not found a contradiction. The next example shows why evenness must not be treated as proof that a realization exists.

Worked Example: An Odd Sum Rules Out a Realization

Could a simple undirected graph on $V=\{1,2,3,4,5\}$ have degree list $(3,2,2,1,1)$? If such a graph existed, its edge set would be some subset of the possible pairs of vertices. Add the proposed degree data: $3+2+2+1+1=9$. Since $9$ is odd, the proposition shows that no such edge set can realize the list.

Check: if there were $m$ edges, the handshake lemma would require $9=2m$, or $m=9/2$. This is not an integer, whereas the number of edges in a finite graph must be an integer. So the contradiction is immediate; no particular candidate edge set can pass the test.

Worked Example: An Even Sum Is Not Enough

Consider the proposed degree list $(2,2,0,0)$ on $V=\{1,2,3,4\}$. Its sum is $2+2+0+0=4$, which is even, and the edge-count formula would give $m=4/2=2$ if a realization existed. Nonetheless, no simple graph on these vertices has this degree list.

To see the contradiction, vertices $3$ and $4$ have degree $0$, so neither can be incident with an edge. Any edges must therefore have both endpoints in $\{1,2\}$. In a simple graph there is at most one edge between those two vertices, namely $12$. Hence each of $1$ and $2$ could have degree at most $1$, contradicting the requested degree $2$ for both.

Check: the parity calculation gives the integer $2$, but the local edge possibilities cannot give the stated degrees. Thus an even sum is necessary, not sufficient, for a degree list to have a realization.

What the Degree List Does—and Does Not—Tell You

When a list is realizable, it fixes the edge count, but it need not fix which pairs of vertices are adjacent. For example, on $V=\{1,2,3,4,5,6\}$, take either $E_1=\{12,23,34,45,56,61\}$ or $E_2=\{12,23,31,45,56,64\}$. Both graphs have degree list $(2,2,2,2,2,2)$. In the first graph, the edges form one cycle through all six vertices; in the second, they form two separate triangles. Each edge set has six edges, in agreement with the degree sum $6\cdot2=12$ and the formula $m=12/2=6$.

In applications, separate three questions. First, if the data are realizable, how many edges must the graph have? The half-sum gives the answer. Second, do the data pass the immediate parity test? Their sum must be even. Third, do the data actually have a realization? The half-sum and parity check alone do not settle that question; the even-sum example above fails for a different reason.

Common Pitfall

Wrong calculation: a student adds the degrees $2,3,2,2,1$ to get $10$ and reports $10$ edges. This counts each edge twice, once at each endpoint. Correction: use the handshake lemma and divide the degree sum by $2$: $m=10/2=5$. The calculation should also be consistent with the edge set, which has five edges.

A related mistake is to say that an even degree sum proves a graph exists. The list $(2,2,0,0)$ has even sum $4$, yet the required degrees cannot be attained in a simple graph on the specified vertices. Use parity as a fast rejection test, not as a complete test of realizability.

Check Your Understanding

For each question, state whether you are calculating the edge count of data assumed to be realizable or testing whether a realization is possible.

A graph has degree list $(1,2,2,3,2)$. If it exists, how many edges must it have?
A proposed list is $(3,2,2,2,1)$. Use its degree sum to decide whether it can be realized.
There are four vertices of degree $2$ and two vertices of degree $1$. If these data are realizable, find the edge count using degree frequencies.
Explain why an even degree sum is necessary but not sufficient for a realization, using the list $(2,2,0,0)$.
Can two graphs with the same degree list have different edge counts? Justify your answer from the edge-count rule.