The Caro-Wei Bound: Random Ordering Proof

The Random-Ordering Idea

An independent set is a set of vertices no two of which are adjacent. The independence number $\alpha(G)$ is the largest size of an independent set in $G$. Rather than search directly for a largest independent set, we can use a random ordering to construct an independent set and calculate its expected size. Since no constructed independent set can be larger than $\alpha(G)$, its expected size gives a lower bound on $\alpha(G)$.

Throughout, $G=(V,E)$ is a finite simple graph, and $d(v)=\deg(v)$ is the number of neighbors of $v$. An ordering is a list of all vertices in which each vertex occurs exactly once. We choose uniformly from the $|V|!$ possible orderings when $V$ is nonempty. Say that $v$ is selected if $v$ occurs before every vertex in its neighborhood $N(v)$.

Definition: Given an ordering of $V$, let $S$ be the set of vertices that occur before all their neighbors. If $v$ has no neighbors, this condition is satisfied: $v$ occurs before every vertex in the empty set.

Each vertex is considered separately. The selection event for $v$ depends only on the relative ordering of $v$ and its neighbors. Among those $d(v)+1$ vertices, each is equally likely to occur first, so $v$'s chance of selection is $1/(d(v)+1)$. The key point is that the vertices selected in any one ordering form an independent set.

Why the Selected Vertices Form an Independent Set

Lemma: For every ordering of the vertices of a simple graph, the set $S$ of vertices that precede all their neighbors is independent.

Proof. Suppose instead that two selected vertices $u$ and $v$ are adjacent. Because $u$ is selected, $u$ occurs before every neighbor of $u$, including $v$. Because $v$ is selected, $v$ occurs before every neighbor of $v$, including $u$. Thus the ordering would place $u$ before $v$ and $v$ before $u$, which is impossible. Hence no two vertices in $S$ are adjacent, so $S$ is independent. $\square$

This argument applies to every ordering, not just to a typical one. In particular, if $\alpha(G)$ is the largest size of an independent set, then $|S|\leq \alpha(G)$ for every outcome of the random experiment.

The Caro–Wei Bound

Theorem (Caro–Wei): For every finite simple graph $G$, $$ \alpha(G)\geq \sum_{v\in V(G)}\frac{1}{d(v)+1}. $$

Proof. First suppose $V$ is nonempty, and choose an ordering uniformly at random. For each vertex $v$, let $I_v$ equal $1$ if $v$ is selected and $0$ otherwise. Then the size of the selected set is $|S|=\sum_{v\in V} I_v$. Among the $d(v)+1$ vertices consisting of $v$ and its neighbors, each is equally likely to be first in their relative order. Exactly one of these vertices is first, and $v$ is selected precisely when $v$ is that first vertex. Therefore the probability that $I_v=1$ is $1/(d(v)+1)$, and its expected value is $\mathbb{E}[I_v]=1/(d(v)+1)$.

By adding these expectations, $\mathbb{E}[|S|]=\sum_{v\in V}1/(d(v)+1)$. The lemma shows that every outcome gives an independent set, so $|S|\leq\alpha(G)$ for every outcome. Taking expectations preserves this inequality and gives the claimed bound. If $V$ is empty, set $\alpha(G)=0$; the sum over the empty vertex set is also $0$, so the inequality holds in that case as well. $\square$

The proof does not require the selection events at different vertices to be independent. In fact, adjacent vertices cannot both be selected. What matters for the expected size is that the size is a sum of indicator variables: the expected value of a finite sum is the sum of the expected values, regardless of dependence.

Worked Examples

Worked Example: The Path on Four Vertices

Let $G=(V,E)$ with $V=\{1,2,3,4\}$ and $E=\{12,23,34\}$. The degrees are $d(1)=1$, $d(2)=2$, $d(3)=2$, and $d(4)=1$. The contribution from each vertex is therefore $1/2$, $1/3$, $1/3$, and $1/2$, respectively. The bound is

\sum_{v\in V}\frac{1}{d(v)+1} =\frac12+\frac13+\frac13+\frac12 =\frac{3+2+2+3}{6} =\frac{10}{6} =\frac53.

For a specific ordering, take $2,1,3,4$. Vertex $2$ occurs before both neighbors $1$ and $3$, so it is selected. Vertex $1$ occurs after its neighbor $2$, so it is not selected; vertex $3$ also occurs after neighbor $2$, and vertex $4$ occurs after neighbor $3$. Thus this ordering produces $S=\{2\}$, which is independent.

Check: The set $\{1,3\}$ is independent, so $\alpha(G)\geq2$. No three vertices are independent: the four possible three-vertex sets are $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,4\}$, and $\{2,3,4\}$; they contain the edges $12$, $12$, $34$, and $23$, respectively. Hence $\alpha(G)=2$, and the computed bound $5/3\leq2$ is valid.

Worked Example: A Star with Three Leaves

Let $G=(V,E)$ with $V=\{c,a,b,e\}$ and $E=\{ca,cb,ce\}$. The center $c$ has degree $3$, and each leaf has degree $1$. The four terms in the bound are $1/4,1/2,1/2,1/2$, giving

\sum_{v\in V}\frac{1}{d(v)+1} =\frac14+\frac12+\frac12+\frac12 =\frac14+\frac64 =\frac74.

For the ordering $a,c,e,b$, leaf $a$ precedes its only neighbor and is selected. The center $c$ does not precede any of its three neighbors, so it is not selected. Leaf $e$ precedes $c$ and is selected; leaf $b$ follows $c$ and is not selected. The resulting set is $\{a,e\}$.

We can check the expected size by conditioning on the center’s position. There are $4!=24$ equally likely orderings. For each possible position of $c$, exactly $3!=6$ orders of the leaves accompany it. If $c$ is first, it is selected and no leaf is, giving size $1$. If $c$ is second, exactly one leaf precedes it, giving size $1$. If $c$ is third, two leaves precede it, giving size $2$. If $c$ is fourth, all three leaves precede it, giving size $3$. The total selected-vertex count across the $24$ orders is $6(1+1+2+3)=42$, so the expected size is $42/24=7/4$, as the vertex-probability calculation gives.

Check: The three leaves form an independent set. Any independent set containing the center contains no leaf, so its size is at most $1$; any independent set omitting the center has size at most $3$. Thus $\alpha(G)=3$, and $7/4\leq3$.

Worked Example: The Complete Graph on Four Vertices

Let $G=(V,E)$, where $V=\{1,2,3,4\}$ and $E=\{12,13,14,23,24,34\}$. Every vertex is adjacent to the other three, so each degree is $3$. Consequently,

\sum_{v\in V}\frac{1}{d(v)+1} =\frac14+\frac14+\frac14+\frac14 =\frac44 =1.

In the ordering $3,1,4,2$, vertex $3$ is first and hence precedes all its neighbors. Each of the other three vertices has $3$ before it as a neighbor, so none of them is selected. The selected set is $\{3\}$. In any ordering of this graph, the first vertex is selected and every other vertex is not: every pair of distinct vertices is adjacent. Of the $24$ orderings, each of the four vertices occurs first in $3!=6$ orderings. Thus the selected set has size $1$ in all $24$ cases, confirming the expected size $1$.

Check: Any two distinct vertices are adjacent, so an independent set contains at most one vertex; a singleton is independent. Therefore $\alpha(G)=1$, and the bound is exact.

Common Pitfall: Counting Only the Neighbors

A frequent error is to say that $v$ has probability $1/d(v)$ of preceding all its neighbors. That counts only the neighbors and leaves out $v$ itself. The relevant relative ordering contains $d(v)+1$ vertices: $v$ and its $d(v)$ neighbors. Each of those vertices is equally likely to be first, so the correct probability is $1/(d(v)+1)$.

For the four-vertex path above, using the incorrect denominator $d(v)$ would give endpoint contributions $1$ and middle-vertex contributions $1/2$, for a purported lower bound $1+1/2+1/2+1=3$. But the path has independence number $2$, as checked above, so that purported bound cannot be right. Using $d(v)+1$ instead gives $5/3$, which is consistent with $\alpha(G)=2$.

What the Bound Guarantees

The random-order argument is a way to prove that at least one independent set is large: if every ordering produced a set smaller than the expected size, the average could not equal that expected size. More precisely, the theorem bounds $\alpha(G)$, the size of a largest independent set; it does not say that every ordering produces an independent set of at least the displayed size. In the path example, the ordering $2,1,3,4$ produced a set of size $1$, even though the expected size was $5/3$.

Isolated vertices are included without special adjustment. If $d(v)=0$, then $v$ precedes all of its neighbors because there are none, so it is selected in every ordering. Its contribution to the sum is $1/(0+1)=1$, as expected. The empty graph is also covered by the theorem: both the independence number and the empty sum are $0$.

The method’s strength comes from using every vertex’s own degree in its contribution. The proof turns those local probabilities into a global guarantee by summing them, while the independence lemma ensures that each outcome is a valid candidate for the independence number. The next step in studying this bound is to evaluate it in graph families where the degree pattern has additional structure.

Check Your Understanding

For each question, distinguish the probability attached to one vertex from the size of the entire selected set.

In a simple graph, why does the relative ordering relevant to selecting $v$ contain $d(v)+1$ vertices rather than $d(v)$?
For the graph with $V=\{1,2,3\}$ and $E=\{12,23\}$, compute the Caro–Wei sum and check it against an independent set of maximum size.
Explain why two adjacent vertices cannot both precede all their neighbors in the same ordering.
If a vertex is isolated, what is its selection probability and what is its contribution to the bound?
Does the theorem claim that every ordering produces a set at least as large as the sum in the bound? Explain the role of expectation.