Applying Caro-Wei to Regular and Sparse Graphs

Using the Degree List

The Caro–Wei bound turns the degrees of a graph into a lower bound on its independence number. Its usefulness is not limited to graphs with a uniform degree: when the full degree list is known, each vertex contributes according to its own degree. This can produce a stronger estimate than one based only on the maximum degree, especially in a graph with a few high-degree vertices and many low-degree ones.

All graphs in this tutorial are finite and simple. An independent set is a set of vertices no two of which are adjacent, and $\alpha(G)$ is the largest size of an independent set in $G$. The degree $d(v)$ is the number of vertices adjacent to $v$; the maximum degree is $\Delta(G)$. An $r$-regular graph is one in which every vertex has degree $r$.

Theorem (Caro–Wei bound): For every finite simple graph $G=(V,E)$, $$ \alpha(G)\geq \sum_{v\in V}\frac{1}{d(v)+1}. $$ The bound is understood to be $0\geq0$ when $V=\varnothing$. For a nonempty graph the sum is positive, and since $\alpha(G)$ is an integer, it is also at least the ceiling of the displayed sum.

The Caro–Wei theorem is proved by the random-ordering argument in the earlier material on this bound. Here we use it to draw consequences from regularity and degree information. Each summand depends on the degree of its own vertex, so replacing the whole list by one degree value is justified only when all degrees are equal.

Regular Graphs and the Maximum-Degree Estimate

If $G$ is $r$-regular on $n$ vertices, then every summand in the Caro–Wei sum is $1/(r+1)$. Thus the bound becomes $n/(r+1)$. For a general graph, each degree satisfies $d(v)\leq\Delta(G)$, so $d(v)+1\leq\Delta(G)+1$; taking positive reciprocals gives a summand at least $1/(\Delta(G)+1)$. Adding over the $n$ vertices gives the maximum-degree bound.

Corollary: If $G$ has $n$ vertices and is $r$-regular, then $$ \alpha(G)\geq \frac{n}{r+1}. $$ For any finite simple graph $G$, $$ \alpha(G)\geq \sum_{v\in V}\frac{1}{d(v)+1}\geq \frac{n}{\Delta(G)+1}. $$

The comparison is term by term. If $G$ is nonempty and at least one vertex has degree strictly less than $\Delta(G)$, its Caro–Wei summand is strictly larger than $1/(\Delta(G)+1)$, while every other summand is at least that value. In that case the degree-list sum is strictly larger than the maximum-degree estimate. The strictness concerns the two estimates; the integer value of $\alpha(G)$ may be larger than either.

Worked Example: A Regular Cycle

Let $G=C_6$, with vertex set $\{1,2,3,4,5,6\}$ and edge set $\{12,23,34,45,56,61\}$. Each vertex has degree $2$, so $G$ is $2$-regular. Its order is $n=6$. The Caro–Wei sum is

\sum_{v\in V}\frac{1}{d(v)+1} =6\left(\frac{1}{2+1}\right) =\frac{6}{3} =2.

The maximum-degree bound gives $n/(\Delta(G)+1)=6/(2+1)=2$, the same estimate. In fact, $\{1,3,5\}$ is independent: the listed edges join consecutive vertices of the cycle, and none has both endpoints in this set. Thus $\alpha(G)\geq3$. No independent set has more than $3$ vertices, since the three disjoint edges $12,34,56$ each contribute at most one vertex to an independent set. Therefore $\alpha(G)=3$.

Check: the degree list has six entries equal to $2$, so its Caro–Wei sum is $6/3=2$; the three disjoint edges also show the upper bound $\alpha(G)\leq3$, matching the displayed independent set. The Caro–Wei bound need not be attained.

A Bound from Average Degree

When the individual degrees are not all available, the edge count gives their sum. The handshake lemma says $\sum_{v\in V}d(v)=2m$, where $m=|E|$. Applying Cauchy–Schwarz to the positive numbers $d(v)+1$ gives another convenient estimate.

Corollary: If $G$ has $n>0$ vertices and $m$ edges, then $$ \alpha(G)\geq \sum_{v\in V}\frac{1}{d(v)+1} \geq \frac{n^2}{n+2m} =\frac{n}{1+2m/n}. $$ Equality in the second inequality holds exactly when all the numbers $d(v)+1$, and hence all the degrees, are equal.

Proof. Put $a_v=d(v)+1$, which is positive for every vertex. Cauchy–Schwarz applied to the lists $\sqrt{a_v}$ and $1/\sqrt{a_v}$ gives $$ \left(\sum_{v\in V}a_v\right)\left(\sum_{v\in V}\frac{1}{a_v}\right)\geq \left(\sum_{v\in V}1\right)^2=n^2. $$ The handshake lemma yields $\sum_{v\in V}a_v=\sum_v(d(v)+1)=2m+n$. Dividing by the positive number $2m+n$ proves the second inequality. Equality in Cauchy–Schwarz holds exactly when the two lists are proportional, which here requires the $a_v$ to be constant. The first inequality is Caro–Wei. $\square$

The quantity $2m/n$ is the average degree. Since it is at most $\Delta(G)$, the average-degree estimate is at least as large as $n/(\Delta(G)+1)$. It may still be weaker than the full degree-list sum: knowing only the average discards information about how the degrees are distributed.

Worked Example: A Star with Unequal Degrees

Let $G$ have vertex set $\{c,1,2,3,4\}$ and edge set $\{c1,c2,c3,c4\}$, so $G=K_{1,4}$. The center $c$ has degree $4$, and each of the four leaves has degree $1$. The full degree-list sum is

\sum_{v\in V}\frac{1}{d(v)+1} =\frac{1}{4+1}+4\left(\frac{1}{1+1}\right) =\frac{1}{5}+2 =\frac{11}{5}.

Thus $\alpha(G)\geq\lceil 11/5\rceil=3$. The maximum-degree estimate is $5/(4+1)=1$, which is strictly smaller than $11/5$. For the average-degree estimate, $n=5$ and $m=4$, so $n^2/(n+2m)=25/(5+8)=25/13$. This is less than $11/5$, since $25/13<11/5$ is equivalent to $125<143$.

The four leaves form an independent set. No independent set containing $c$ can contain a leaf, while a set not containing $c$ has at most the four leaves; hence $\alpha(G)=4$. Check: the edge count is $4$, and the degree sum is $4+1+1+1+1=8=2m$, as required by the handshake lemma. The computed estimates are $11/5$, $1$, and $25/13$, respectively.

Equality in the Regular Case

For regular graphs there is a precise description of equality: the bound is attained exactly by disjoint unions of cliques of the same size. In an $r$-regular graph, every such clique must have $r+1$ vertices. The proof uses a maximum independent set to partition the vertices into closed neighborhoods.

Theorem: Let $G$ be a finite, nonempty, $r$-regular simple graph. Then $$ \alpha(G)=\frac{|V(G)|}{r+1} $$ if and only if $G$ is a disjoint union of cliques, each of order $r+1$.

Proof. First suppose $G$ is a disjoint union of $q$ cliques, each of order $r+1$. Each clique contributes $r+1$ vertices, so $n=q(r+1)$. An independent set contains at most one vertex from each clique, and choosing one vertex from each gives an independent set of size $q$. Therefore $\alpha(G)=q=n/(r+1)$.

Conversely, suppose $G$ is $r$-regular and $\alpha(G)=n/(r+1)$. Choose a maximum independent set $I$. For each $v\in I$, let $N[v]$ denote the closed neighborhood consisting of $v$ and all its neighbors. Since $G$ is $r$-regular, each $N[v]$ has $r+1$ vertices. The sets $N[v]$, for $v\in I$, cover $V$: if a vertex outside $I$ had no neighbor in $I$, it could be added to $I$, contradicting maximal size. Their total size is $|I|(r+1)=n$. A cover of an $n$-element set by finite sets whose sizes sum to $n$ has no overlap, so these closed neighborhoods partition $V$.

Fix $v\in I$. If two distinct neighbors $x,y$ of $v$ were nonadjacent, then both belong to $N[v]\setminus\{v\}$. Neither can be adjacent to a different vertex $u\in I$: such adjacency would put that vertex in both $N[v]$ and $N[u]$, contradicting disjointness. Also, $x$ and $y$ are not in $I$, since each is adjacent to $v\in I$. Replacing $v$ by $x,y$ would therefore produce an independent set of size $|I|+1$, a contradiction. Thus the neighbors of $v$ are pairwise adjacent, and $N[v]$ is a clique of order $r+1$. Every vertex in this clique already has $r$ neighbors inside it; regularity leaves no edges from the clique to any vertex outside it. Since the sets $N[v]$ partition $V$, the graph is a disjoint union of these cliques. $\square$

Worked Example: Two Equal Cliques

Let $G$ have vertex set $\{1,2,3,4,5,6\}$ and edge set $\{12,13,23,45,46,56\}$. This is a disjoint union of two triangles. Every vertex has degree $2$, so $G$ is $2$-regular, with $n=6$. The Caro–Wei sum is $6/(2+1)=2$.

An independent set can contain at most one vertex from $\{1,2,3\}$ and at most one from $\{4,5,6\}$, so its size is at most $2$. The set $\{1,4\}$ is independent because the edge list contains no edge between the two triangles. Hence $\alpha(G)=2$, equal to the Caro–Wei bound.

Check: there are $3+3=6$ edges, and the degree sum is $6\cdot2=12=2|E|$. The two cliques each have order $3=r+1$, as required by the equality theorem.

Common Pitfall

A frequent error is to use the maximum degree in every term of the degree-list sum. For the star above, writing $5\left(1/(4+1)\right)=1$ is not the Caro–Wei calculation: it replaces the four leaf degrees, each equal to $1$, by the center's degree $4$. The correct sum is $1/5+4(1/2)=11/5$. The expression $n/(\Delta(G)+1)$ is a valid, potentially weaker bound; it should not be confused with the degree-list bound. More generally, the degree-list calculation requires the degree of each vertex, while the maximum-degree estimate requires only $n$ and $\Delta(G)$.

Check Your Understanding

For each question, distinguish the bound using the full degree list from a bound using only the maximum degree.

A $3$-regular graph has $12$ vertices. What lower bound does Caro–Wei give, and what is its maximum-degree bound?
For the graph with vertex set $\{1,2,3,4\}$ and edge set $\{12,23,34\}$, compute the degree-list sum and compare it with $n/(\Delta(G)+1)$.
Show that if at least one vertex of a nonempty graph has degree less than $\Delta(G)$, the degree-list sum is strictly greater than $n/(\Delta(G)+1)$.
Why does equality in the average-degree estimate require all degrees to be equal?
For a nonempty $r$-regular graph attaining equality in Caro–Wei, what is the order of each clique in its decomposition?