Averaging Arguments From Degree Sums

From a Total to a Vertex

A graph argument often needs one particular vertex with a useful property: perhaps its degree is small enough to remove, or it has few neighbors in a specified set. Rather than identify that vertex directly, one can add the relevant counts over all vertices, divide by their number, and compare the average with the required bound. The key is to use the average correctly: it guarantees that at least one value is no greater than the average and at least one is no less.

Throughout, graphs are finite and simple. For a vertex $v$, its degree $\deg(v)$ is the number of its neighbors, so $\deg(v)=|N(v)|$. Write $n=|V(G)|$ and $m=|E(G)|$. Averages over vertices require $n>0$; a sum over no vertices does not provide an average.

Definition: The average degree of a graph with at least one vertex is $$ \overline d(G)=\frac{1}{n}\sum_{v\in V(G)}\deg(v). $$ The handshake lemma gives $\sum_{v\in V(G)}\deg(v)=2m$, because each edge contributes one to the degree of each of its two endpoints. Consequently, $\overline d(G)=2m/n$.

The average is a real number, while each degree is an integer. That distinction often turns an average bound into a sharper integer bound. For example, if the average is strictly less than $r$, at least one degree is at most $r-1$, when $r$ is an integer.

The Basic Averaging Principle

Theorem: In any graph $G$ with $n>0$, there is a vertex $u$ with $\deg(u)\le 2m/n$, and there is a vertex $w$ with $\deg(w)\ge 2m/n$. In particular, if $2m/n<r$ for an integer $r$, then some vertex has degree at most $r-1$; if $2m/n>r$, some vertex has degree at least $r+1$.

Proof. Suppose every vertex had degree greater than $2m/n$. Adding these $n$ strict inequalities would give $\sum_v\deg(v)>n(2m/n)=2m$, contradicting the degree-sum formula. Therefore some vertex has degree at most $2m/n$. If instead every vertex had degree less than $2m/n$, adding would give $\sum_v\deg(v)<2m$, also a contradiction. Hence some vertex has degree at least $2m/n$. For the integer consequences, a degree at most a real number strictly below the integer $r$ must be at most $r-1$; a degree at least a real number strictly above $r$ must be at least $r+1$. $\square$

The weak inequalities in the first two conclusions matter: the average itself can be attained. The strict comparisons in the integer consequences matter too. An average equal to $r$ guarantees a degree at most $r$, not necessarily at most $r-1$.

Worked Example: Locate Vertices on Both Sides of the Average

Let $G$ have $V(G)=\{1,2,3,4,5,6\}$ and $E(G)=\{12,13,23,24,35,45,56\}$. Find its average degree and verify the guaranteed low- and high-degree choices.

Counting incident edges at each vertex gives $\deg(1)=2$, $\deg(2)=3$, $\deg(3)=3$, $\deg(4)=2$, $\deg(5)=3$, and $\deg(6)=1$. The sum is $2+3+3+2+3+1=14$, and there are $m=7$ edges, so the handshake check is $2m=2(7)=14$. Thus the average degree is $14/6=7/3$.

Vertex $6$ has degree $1\le 7/3$, and vertex $2$ has degree $3\ge 7/3$. Since $7/3<3$, the integer version guarantees a vertex of degree at most $2$; vertices $1,4,6$ meet that bound. Since $7/3>2$, it also guarantees a vertex of degree at least $3$; vertices $2,3,5$ meet that bound.

Check: The six degrees sum to $14$, and $14/6=7/3$. The displayed low- and high-degree vertices therefore lie on the claimed sides of the computed average.

Neighborhood Counts Between Sets

The same idea works when the count of interest is not the full degree. Let $A$ and $B$ be disjoint vertex sets. For each $a\in A$, count only its neighbors in $B$. Each edge with one endpoint in $A$ and the other in $B$ contributes exactly once to the total of these counts.

Proposition: Let $A,B\subseteq V(G)$ be disjoint, with $A\ne\varnothing$. Let $e(A,B)$ be the number of edges with one endpoint in $A$ and one in $B$. Then some $a\in A$ satisfies $$ |N(a)\cap B|\le \frac{e(A,B)}{|A|}. $$ If $e(A,B)<r|A|$ for an integer $r$, then some $a\in A$ has at most $r-1$ neighbors in $B$.

Proof. Sum $|N(a)\cap B|$ over all $a\in A$. Every edge between $A$ and $B$ is counted once, at its endpoint in $A$, and no other edge is counted. Therefore $\sum_{a\in A}|N(a)\cap B|=e(A,B)$. If every count were greater than $e(A,B)/|A|$, their sum would be greater than $e(A,B)$, a contradiction. This proves the weak bound. Under the strict hypothesis $e(A,B)<r|A|$, the average is strictly less than $r$; since each count is an integer, some count is at most $r-1$. $\square$

Worked Example: Find a Vertex with Few Neighbors Across a Partition

Let $G$ have vertex set $A\cup B$, where $A=\{a,b,c,d\}$, $B=\{x,y,z\}$, and edge set $E(G)=\{ax,ay,bx,by,bz,cx,dz\}$. There are no other edges. Find a vertex in $A$ with at most one neighbor in $B$.

Check: The listed edges give $c$ the sole neighbor $x$ in $B$, and $d$ the sole neighbor $z$ in $B$. Each therefore meets the asserted bound.

There is also a useful consequence for large degrees. For a positive real number $t$, let $H$ be the set of vertices whose degree is at least $t$. Then $t|H|\le\sum_{v\in H}\deg(v)\le 2m$, so $|H|\le 2m/t$. This bounds how many vertices can have a degree at or above a chosen threshold; the threshold condition here is $\deg(v)\ge t$, not $\deg(v)>t$.

Worked Example: Bound the Number of High-Degree Vertices

Use the graph from the first example, which has $2m=14$, to bound the number of vertices of degree at least $3$, and check the result directly.

Taking $t=3$, the bound gives $|H|\le 14/3$. Since $|H|$ is an integer, this implies $|H|\le4$. From the computed degrees $2,3,3,2,3,1$, the vertices with degree at least $3$ are exactly $2,3,5$, so $|H|=3$.

Check: The high-degree vertices contribute $3+3+3=9$ to the total degree, and $9\le14$. The direct count $3$ satisfies the derived bound of at most $4$.

Using a Low-Degree Choice in a Coloring Argument

Averaging becomes especially useful when the low-degree choice can be repeated after deleting a vertex. A proper coloring assigns colors to vertices so that adjacent vertices have different colors. The next result shows how a condition on every induced subgraph supplies a safe deletion at each stage.

Theorem: Let $k$ be a positive integer. Suppose every nonempty set $S\subseteq V(G)$ satisfies $e(S)<k|S|$, where $e(S)$ is the number of edges in the induced subgraph $G[S]$. Then $G$ has a proper coloring with $2k$ colors.

Proof. If $V(G)=\varnothing$, the empty coloring is proper. Otherwise, consider any nonempty set $S$ and the induced graph $G[S]$. Its average degree is $2e(S)/|S|<2k$. The averaging theorem and integrality of degrees give a vertex in $S$ with at most $2k-1$ neighbors in $G[S]$. Starting with $S=V(G)$, remove such a vertex, and repeat on the remaining set whenever it is nonempty. The hypothesis applies at every step because each remaining set is a subset of $V(G)$. This produces an ordering $v_1,\ldots,v_n$ in which each $v_i$ has at most $2k-1$ neighbors among $v_{i+1},\ldots,v_n$. Now color in reverse order. When $v_i$ is colored, at most $2k-1$ already colored neighbors can forbid colors. Among $2k$ available colors, at least one remains. Choosing it preserves proper coloring among the vertices colored so far. After the last step, every edge has differently colored endpoints, so the coloring is proper. $\square$

Worked Example: Delete and Reinsert Vertices in a Path

Let $G=P_5$ have $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{12,23,34,45\}$. Take $k=1$. Every nonempty induced subgraph of this path is a disjoint union of paths and isolated vertices, so it has at most $|S|-1$ edges, and hence $e(S)<|S|$. The theorem guarantees a proper coloring with $2$ colors.

Choose and delete vertices in the order $1,5,2,4,3$. The table records the remaining graph just before each deletion; its degree column counts neighbors among the vertices still present.

Vertex deleted	Vertices remaining before deletion	Degree at deletion
1	$\{1,2,3,4,5\}$	1
5	$\{2,3,4,5\}$	1
2	$\{2,3,4\}$	1
4	$\{3,4\}$	1
3	$\{3\}$	0

Reinsert in reverse order. Give vertex $3$ color red. Vertex $4$, adjacent to $3$, receives blue; vertex $2$, also adjacent to $3$, receives blue. Vertex $5$, adjacent to $4$, receives red, and vertex $1$, adjacent to $2$, receives red. Thus the colors along the path are red, blue, red, blue, red.

Check: The four edges $12,23,34,45$ join red to blue in each case. The deletion degrees are all at most $1=2k-1$, as required by the argument.

Common Pitfall: Confusing the Average with an Actual Degree

The average degree need not be the degree of any vertex. In the first worked example, the average is $7/3$, but every degree is an integer, so no vertex has degree $7/3$. The valid conclusions are that some degree is at most $7/3$ and some degree is at least $7/3$; they do not assert equality.

A related arithmetic error is to use $m/n$ as the average degree. In $P_4$, with vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34\}$, the degrees are $1,2,2,1$, with sum $6$. The average degree is $6/4=1.5$, equivalently $2m/n=2(3)/4=1.5$. The incorrect calculation $m/n=3/4$ counts each edge only once, although it contributes to the degrees of two endpoints.

Finally, check the set over which the average is taken. A bound on the average degree of all of $G$ gives a low-degree vertex in $G$; it does not automatically give the same bound inside every subset. In the coloring theorem, the hypothesis is deliberately imposed on every nonempty $S$, which is why the low-degree choice remains available after each deletion.

Check Your Understanding

For each question, identify the total being averaged and state whether the relevant bound is strict or non-strict.

A graph has $9$ vertices and $18$ edges. What degree bound does averaging guarantee for at least one vertex?
If $e(A,B)=11$ and $|A|=5$ for disjoint sets $A,B$, what bound on $|N(a)\cap B|$ is guaranteed for some $a\in A$?
Why does an average degree strictly less than the integer $r$ guarantee a degree at most $r-1$, while an average equal to $r$ does not?
A graph has $30$ total degree incidences. How many vertices can have degree at least $6$? Give the averaging bound.
In the coloring theorem, explain why the density hypothesis must apply to every nonempty vertex subset, not just to $V(G)$.

Vertex deleted	Vertices remaining before deletion	Degree at deletion
1	\(\{1,2,3,4,5\}\)	1
5	\(\{2,3,4,5\}\)	1
2	\(\{2,3,4\}\)	1
4	\(\{3,4\}\)	1
3	\(\{3\}\)	0