Degree Sums Across Vertex Subsets

Counting Degrees on a Vertex Subset

The handshake lemma counts the incidences between vertices and edges in a whole graph: each edge contributes two to the sum of all degrees. For a selected set of vertices, an edge can contribute differently depending on where its endpoints lie. An edge with both endpoints selected contributes twice; an edge with just one selected endpoint contributes once; an edge with neither endpoint selected contributes nothing. Making this distinction gives a degree-sum identity for every vertex subset.

Throughout, $G=(V,E)$ is a finite simple graph. For $S\subseteq V$, write $V\setminus S$ for the vertices outside $S$. An edge is internal to $S$ if both its endpoints belong to $S$, and it crosses from $S$ to $V\setminus S$ if exactly one endpoint belongs to $S$. Edges with both endpoints outside $S$ are neither internal to $S$ nor crossing edges.

Definition: Let $e_G(S)$ denote the number of edges internal to $S$, and let $b_G(S)$ denote the number of edges crossing from $S$ to $V\setminus S$. The degree sum on $S$ is $\sum_{v\in S}\deg(v)$. The subscript $G$ may be omitted when the graph is understood.

These definitions also apply when $S=\varnothing$ or $S=V$. If $S=\varnothing$, the degree sum, the number of internal edges, and the number of crossing edges are all zero. If $S=V$, every edge is internal and there are no crossing edges. A vertex of degree zero contributes zero to a degree sum.

The Degree-Sum Identity

Theorem: For every finite simple graph $G=(V,E)$ and every subset $S\subseteq V$, $$ \sum_{v\in S}\deg(v)=2e_G(S)+b_G(S). $$

Proof. Count the incidences between edges and their endpoints that belong to $S$. An incidence here is a pair consisting of an edge and one of its endpoints in $S$. Counting by vertices gives $\sum_{v\in S}\deg(v)$, because each edge incident with $v\in S$ contributes one incidence at $v$. Now count by edges. Each edge internal to $S$ has two endpoints in $S$, so contributes two incidences. Each edge crossing from $S$ to $V\setminus S$ has one endpoint in $S$, so contributes one. An edge with both endpoints outside $S$ contributes zero. These are all the possible cases, so the total is $2e_G(S)+b_G(S)$. This reasoning also covers $S=\varnothing$ and $S=V$, since the same edge-by-edge counts apply. $\square$

The coefficient of $e_G(S)$ is two because every internal edge has two endpoints in the selected set. The coefficient of $b_G(S)$ is one because a crossing edge has just one endpoint there. Edges entirely outside $S$ do not enter the sum at all.

Worked Example: Counting Internal and Crossing Edges

Let $G=(V,E)$ have $V=\{1,2,3,4,5,6\}$ and $E=\{12,13,23,24,34,45,56,46\}$. Take $S=\{1,2,4,5\}$, so $V\setminus S=\{3,6\}$. Compute the degree sum on $S$ and check it using the identity.

From the edge list, vertex $1$ is incident with $12,13$, so $\deg(1)=2$. Vertex $2$ is incident with $12,23,24$, so $\deg(2)=3$. Vertex $4$ is incident with $24,34,45,46$, so $\deg(4)=4$. Vertex $5$ is incident with $45,56$, so $\deg(5)=2$. Therefore the degree sum on $S$ is $2+3+4+2=11$.

The edges internal to $S$ are $12,24,45$, giving $e_G(S)=3$. The crossing edges are $13,23,34,46,56$, giving $b_G(S)=5$. Substitution into the identity gives $2e_G(S)+b_G(S)=2(3)+5=6+5=11$, agreeing with the degree sum.

Check: The edge $36$ is not in $E$, so there are no edges internal to $V\setminus S$. The eight listed edges split into three internal to $S$, five crossing, and zero internal to its complement: $3+5+0=8=|E|$.

How the Edges Split Across a Set

Every edge belongs to exactly one of three categories: internal to $S$, crossing between $S$ and its complement, or internal to the complement. This gives another useful identity for the edge counts.

Proposition: For every $S\subseteq V$, $$ |E|=e_G(S)+b_G(S)+e_G(V\setminus S). $$

Proof. Consider any edge $uv\in E$. If both $u$ and $v$ belong to $S$, it is counted in $e_G(S)$. If exactly one belongs to $S$, it is counted in $b_G(S)$. If neither belongs to $S$, both endpoints belong to $V\setminus S$, and it is counted in $e_G(V\setminus S)$. These cases are mutually exclusive and cover every edge. Thus counting all edges by these three categories gives the stated sum. $\square$

Worked Example: A Selected Set in a Graph with an Isolated Vertex

Let $G=(V,E)$ have $V=\{1,2,3,4,5,6,7\}$ and $E=\{12,23,34,14,45,56\}$. Vertex $7$ is isolated. Take $S=\{2,4,5,7\}$, whose complement is $\{1,3,6\}$.

From the edge list, vertices $2,4,5,7$ have degrees $2,3,2,0$, respectively. Their degree sum is $2+3+2+0=7$. The only edge with both endpoints in $S$ is $45$, so $e_G(S)=1$. The edges crossing to the complement are $12,23,34,14,56$, so $b_G(S)=5$. The identity gives $2e_G(S)+b_G(S)=2(1)+5=2+5=7$.

Check: There are six edges in total. One is internal to $S$, five cross, and none is internal to the complement, so $1+5+0=6=|E|$. The isolated vertex contributes zero to the degree sum and belongs to neither an internal edge nor a crossing edge.

The edge-splitting proposition and the degree-sum identity can be used together. For example, the degree sum on the complement counts each internal edge there twice and each crossing edge once. Adding the two degree sums counts every edge twice overall.

Corollary: For every $S\subseteq V$, $$ \sum_{v\in S}\deg(v)+\sum_{v\in V\setminus S}\deg(v)=2|E|. $$

Proof. Apply the degree-sum identity to $S$ and to $V\setminus S$. The first sum is $2e_G(S)+b_G(S)$, and the second is $2e_G(V\setminus S)+b_G(V\setminus S)$. An edge crosses the partition $S,V\setminus S$ in either direction, so $b_G(V\setminus S)=b_G(S)$. Adding the expressions gives $2e_G(S)+2b_G(S)+2e_G(V\setminus S)$. By the edge-splitting proposition this equals $2|E|$, as required. The argument remains valid when either part is empty. $\square$

A Parity Consequence

The identity also determines the parity of the degree sum on $S$. An even number of internal-edge contributions is always added, so the parity is controlled by the crossing-edge count.

Corollary: For every $S\subseteq V$, the sum $\sum_{v\in S}\deg(v)$ is even if and only if $b_G(S)$ is even.

Proof. By the degree-sum identity, $\sum_{v\in S}\deg(v)=2e_G(S)+b_G(S)$. The term $2e_G(S)$ is even. Adding an even integer does not change parity, so the degree sum and $b_G(S)$ have the same parity. Hence one is even exactly when the other is even. $\square$

Worked Example: Using the Parity Check

Let $G=(V,E)$ have $V=\{a,b,c,d,e\}$ and $E=\{ab,ac,ad,bc,cd\}$. Choose $S=\{a,b,c\}$, so $V\setminus S=\{d,e\}$.

From the edge list, $\deg(a)=3$, since $a$ is incident with $ab,ac,ad$; $\deg(b)=2$, from $ab,bc$; and $\deg(c)=3$, from $ac,bc,cd$. The degree sum on $S$ is $3+2+3=8$. The internal edges are $ab,ac,bc$, so $e_G(S)=3$. The crossing edges are $ad,cd$, so $b_G(S)=2$. The identity gives $2(3)+2=6+2=8$.

Check: Both the degree sum $8$ and the crossing count $2$ are even, as the parity corollary requires. The five edges split into three internal to $S$, two crossing, and zero internal to the complement: $3+2+0=5=|E|$.

Common Mistake and Uses

A frequent error is to count each edge internal to $S$ only once. In the first worked example, this mistake would give $e_G(S)+b_G(S)=3+5=8$, not the actual degree sum $11$. The correction is to return to the definition of degree: each of the three internal edges has two endpoints in $S$, so each contributes two to the sum. The correct calculation is $2e_G(S)+b_G(S)=2(3)+5=11$.

Another useful check is to count the crossing edges from their endpoints: each crossing edge contributes exactly one to the degree sum on $S$, regardless of which endpoint lies in $S$. Edges with both endpoints outside $S$ contribute nothing, even if they are numerous. The set $S$ need not be connected, and it may include isolated vertices; the identity depends only on whether each edge has zero, one, or two endpoints in $S$.

The formula is useful whenever degree information is grouped by a chosen set of vertices. If no edge has both endpoints in $S$, then $e_G(S)=0$, and the degree sum on $S$ equals the number of edges crossing out of $S$. More generally, knowing any two of the degree sum, internal-edge count, and crossing-edge count determines the third through the identity.

Check Your Understanding

For each question, distinguish internal edges from crossing edges before applying the formula.

Suppose $e_G(S)=4$ and $b_G(S)=3$. What is $\sum_{v\in S}\deg(v)$?
In a graph with $V=\{1,2,3,4\}$ and $E=\{12,13,23,34\}$, take $S=\{1,2\}$. Compute the degree sum directly and using the identity.
Prove directly from the degree-sum identity that if $b_G(S)=0$, then $\sum_{v\in S}\deg(v)$ is even.
If $S$ contains an isolated vertex, explain how that vertex affects $e_G(S)$, $b_G(S)$, and the degree sum.
Explain why an edge with both endpoints outside $S$ contributes zero to $\sum_{v\in S}\deg(v)$.