Comparing Degree-Based Bounds on Explicit Graphs

Two Bounds, Two Different Questions

The Caro–Wei and Wilf bounds use degrees and spectral information to estimate different graph parameters. Caro–Wei gives a lower bound for the independence number \(\alpha(G)\), while Wilf gives an upper bound for the chromatic number \(\chi(G)\). Comparing each bound with the exact value on familiar graph families helps show both what the estimates capture and where they can be loose.

Throughout, graphs are finite and simple. An independent set is a set of vertices no two of which are adjacent; \(\alpha(G)\) is the largest size of such a set. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors; \(\chi(G)\) is the minimum number of colors in a proper coloring. The degree of \(v\) is \(\deg(v)\). The adjacency matrix of \(G\) is denoted by \(\mathbf A(G)\), and its spectral radius \(\rho(G)\) is the largest absolute value of its eigenvalues.

The Caro–Wei inequality is the standard result proved by the random-ordering argument in the earlier material on independence bounds. Wilf’s bound is the standard result established in the earlier material on critical subgraphs and chromatic bounds. We use both in their stated forms: Caro–Wei applies to every finite simple graph, including graphs with isolated vertices, and Wilf’s bound applies to every finite simple graph. Neither inequality asserts equality.

Paths: Degree Sums Can Be Weaker Than Exact Alternation

For \(n\geq 1\), let \(P_n\) have vertex set \(\{1,\ldots,n\}\) and edge set \(\{i(i+1):1\leq i<n\}\). For \(n\geq2\), its two endpoints have degree \(1\), and its other \(n-2\) vertices have degree \(2\). Its exact independence number is \(\lceil n/2\rceil\): choosing vertices \(1,3,5,\ldots\) gives that many, while partitioning the path into consecutive adjacent pairs (with one vertex left over if \(n\) is odd) shows that no independent set can be larger. The alternating two-coloring proves \(\chi(P_n)=2\) for \(n\geq2\); for \(P_1\), both \(\alpha\) and \(\chi\) equal \(1\).

For a general path \(P_n\), the endpoint degrees contribute \(1/2+1/2=1\), and the \(n-2\) internal vertices contribute \((n-2)/3\). Thus for \(n\geq2\) the sum is \((n+1)/3\). This degree calculation does not use the alternating structure that gives the exact independence number, so it can be substantially smaller.

Cycles: Parity Determines the Exact Values

For \(n\geq3\), let \(C_n\) have vertex set \(\{1,\ldots,n\}\) and edges \(12,23,\ldots,(n-1)n,n1\). Every vertex has degree \(2\), so Caro–Wei gives \(n/3\). The exact independence number is \(\lfloor n/2\rfloor\): taking alternate vertices gives this many, and each chosen vertex in an independent set must be followed around the cycle by an unchosen vertex, so there can be no more chosen than unchosen vertices.

If \(n\) is even, alternate two colors around the cycle, giving \(\chi(C_n)=2\). If \(n\) is odd, alternating two colors along the first \(n-1\) vertices leaves the last vertex adjacent to vertices of both colors, so two colors do not suffice. Three colors do suffice: alternate two colors along vertices \(1,\ldots,n-1\), then give vertex \(n\) a third color. Therefore \(\chi(C_n)=3\) for odd \(n\).

Regular Graphs: Both Bounds Simplify

Suppose \(G\) is a \(d\)-regular graph on \(n\geq1\) vertices, meaning every vertex has degree \(d\). Every term in the Caro–Wei sum is \(1/(d+1)\), so

For \(d\geq0\), the adjacency matrix has every row sum \(d\), so the all-ones vector is an eigenvector with eigenvalue \(d\). For \(d>0\), this vector is positive and the graph need not be connected: the Perron–Frobenius theorem applied component by component, or the row-sum bound on eigenvalues, gives \(\rho(G)=d\). For \(d=0\), the adjacency matrix is zero and the same equality holds. Thus Wilf gives \(\chi(G)\leq d+1\).

These formulas are not generally exact. For the complete graph \(K_{d+1}\), with \(d+1\geq1\), every vertex has degree \(d\), and no two vertices are independent. Hence \(\alpha(K_{d+1})=1\), equal to the Caro–Wei sum \((d+1)/(d+1)=1\). Every vertex of \(K_{d+1}\) needs its own color, so \(\chi(K_{d+1})=d+1\); because \(\rho(K_{d+1})=d\), Wilf’s bound is exact as well. This includes the one-vertex graph when \(d=0\).

Complete Bipartite Graphs: Unequal Degrees, Simple Exact Values

Let \(K_{m,n}\) have two disjoint parts \(X,Y\), with \(|X|=m\geq1\) and \(|Y|=n\geq1\), and have every possible edge between \(X\) and \(Y\) and no edges within either part. Vertices in \(X\) have degree \(n\); vertices in \(Y\) have degree \(m\). Consequently the Caro–Wei sum is

An independent set cannot include a vertex from each part, since every cross-part pair is adjacent. It is therefore contained in one part, and the larger part itself is independent; hence \(\alpha(K_{m,n})=\max(m,n)\). The graph has an edge, so at least two colors are necessary, and coloring each part with its own color shows \(\chi(K_{m,n})=2\).

For any \(m,n\geq1\), the spectral radius calculation generalizes: assign \(\sqrt n\) to vertices in \(X\) and \(\sqrt m\) to vertices in \(Y\). The neighbor sums are \(n\sqrt m=\sqrt{mn}\sqrt n\) on \(X\) and \(m\sqrt n=\sqrt{mn}\sqrt m\) on \(Y\). Positivity and connectedness give \(\rho(K_{m,n})=\sqrt{mn}\). Wilf’s estimate is therefore \(2\leq1+\sqrt{mn}\). It is sharp exactly when \(mn=1\), that is, for \(K_{1,1}\); otherwise its right-hand side is greater than \(2\).

How to Judge Sharpness—and a Common Error

An estimate is sharp on a particular graph when its bound equals the exact parameter it bounds. For Caro–Wei, compare the degree sum with \(\alpha(G)\); for Wilf, compare \(1+\rho(G)\) with \(\chi(G)\), remembering that integrality can make the resulting integer bound tighter than the real-valued expression. The examples illustrate that sharpness is separate for the two bounds: on \(C_5\), Wilf is sharp but Caro–Wei is not; on \(K_4\), both are sharp; on \(K_{2,3}\), neither is.

Common mistake: guessing a path’s spectral radius from a convenient vector. For \(P_4\), the vector \((1,\sqrt2,\sqrt2,1)\) is not an eigenvector: the neighbor sum at vertex \(2\) is \(1+\sqrt2\), whereas \(\sqrt2\) times its entry is \(2\), and \(1+\sqrt2\ne2\). The correct positive eigenvector is \((1,\varphi,\varphi,1)\), with \(\varphi=(1+\sqrt5)/2\), because \(\varphi^2=1+\varphi\). This gives \(\rho(P_4)=\varphi\) and Wilf’s bound \(1+\varphi\), not \(1+\sqrt2\). An eigenvalue claim must satisfy the eigenvector equation at every vertex.

The bounds are useful because they turn local degree information or a spectral quantity into global information about independent sets or colorings. Their comparison with exact values also signals when more structural information is needed: the degree sum alone does not encode the alternating pattern in a path, while regularity makes both formulas especially transparent.