From Coloring to Spectral Radius
A graph may require many colors even when its vertices have relatively few neighbors. The maximum-degree coloring bound uses only the largest degree; Wilf’s bound instead uses the adjacency-matrix spectral radius, which reflects the graph’s overall adjacency structure. Its proof links coloring to degree in a carefully chosen subgraph: a vertex-critical subgraph.
Throughout, graphs are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices receive different colors, and the chromatic number \(\chi(G)\) is the least number of colors in such a coloring. We use the convention \(\chi(G)=0\) if \(V(G)=\varnothing\). The adjacency matrix \(\mathbf A(G)\) has entry \(1\) in positions corresponding to adjacent vertices and \(0\) otherwise; its spectral radius \(\rho(G)\) is the largest absolute value of its eigenvalues. For the empty graph, whose adjacency matrix has no eigenvalues, we separately set \(\rho(G)=0\) by convention.
A vertex-critical graph is minimal under vertex deletion for retaining its chromatic number. Every nonempty graph \(G\) with \(\chi(G)=k\) has an induced vertex-critical subgraph with chromatic number \(k\): among the induced subgraphs of \(G\) having chromatic number \(k\), choose one of least order. Deleting any vertex gives a proper induced subgraph, which cannot still have chromatic number \(k\) by minimality. Its chromatic number is therefore less than \(k\).
The Two Ingredients
Proof. Fix any vertex \(v\in V(H)\). Since \(H\) is vertex-critical, \(H-v\) has a proper coloring using at most \(k-1\) colors. Suppose that \(\deg_H(v)\leq k-2\). The neighbors of \(v\) then receive at most \(k-2\) distinct colors, because there are at most \(k-2\) neighbors. Among a palette of \(k-1\) colors, at least one is absent from those neighbors. Assign that color to \(v\); the coloring remains proper, so \(H\) has a coloring using at most \(k-1\) colors. This contradicts \(\chi(H)=k\). Thus every vertex has degree at least \(k-1\), and \(\delta(H)\geq k-1\). \(\square\)
For the spectral ingredient, recall two elementary facts about real symmetric matrices. The spectral theorem gives real eigenvalues and an orthonormal basis of eigenvectors; the Rayleigh–Ritz formula says that the largest eigenvalue is the maximum of \(x^{T}\mathbf A x/(x^{T}x)\) over nonzero real vectors \(x\). The next lemma explains how these facts apply to graph adjacency matrices, including the empty-graph case.
Proof. Suppose first that \(G\) has \(n\geq1\) vertices, and write \(\lambda_{\max}\) for the largest eigenvalue of \(\mathbf A(G)\). This matrix is real symmetric, so Rayleigh–Ritz applies. Its diagonal entries are zero, and hence a coordinate unit vector has Rayleigh quotient \(0\); consequently \(\lambda_{\max}\geq0\). For every real vector \(x\), let \(|x|\) denote the vector of absolute values of its coordinates. Since every entry of \(\mathbf A(G)\) is nonnegative, the triangle inequality gives \(\left|x^{T}\mathbf A(G)x\right|\leq |x|^{T}\mathbf A(G)|x|\leq\lambda_{\max}x^{T}x\). Applying this to an eigenvector for any eigenvalue \(\lambda\) shows \(|\lambda|\leq\lambda_{\max}\). Since \(\lambda_{\max}\) is itself an eigenvalue, it follows that \(\rho(G)=\lambda_{\max}\).
Let \(\mathbf 1\) be the all-ones vector. Every edge contributes twice to the sum of the entries of \(\mathbf A(G)\), once in each direction. Thus \(\mathbf 1^{T}\mathbf A(G)\mathbf 1=2|E(G)|\), and Rayleigh–Ritz gives \(2|E(G)|/|V(G)|\leq\lambda_{\max}=\rho(G)\). In particular, the average degree is at most \(\rho(G)\), so \(\delta(G)\leq\rho(G)\) for every nonempty \(G\).
Now let \(H\) be a nonempty induced subgraph of \(G\). Take any nonzero vector indexed by \(V(H)\) and extend it to \(V(G)\) by assigning zero to every vertex outside \(H\). Because \(H\) is induced, the extended vector has the same squared length and the same adjacency quadratic form as before extension. Its Rayleigh quotient is therefore unchanged. The maximum Rayleigh quotient over vectors indexed by \(V(G)\) is at least the maximum over these extended vectors, so \(\lambda_{\max}(H)\leq\lambda_{\max}(G)\). The equality of largest eigenvalue and spectral radius just proved gives \(\rho(H)\leq\rho(G)\). If \(H\) is empty, the inequality follows directly from \(\rho(H)=0\) and \(\rho(G)\geq0\). \(\square\)
The average-degree inequality in the lemma is stated only for nonempty graphs, so its denominator is defined. The largest-eigenvalue claim is also restricted to nonempty graphs: an empty adjacency matrix has no eigenvalues. The convention \(\rho(\varnothing)=0\) is enough for the monotonicity statement when an induced subgraph is empty.
Wilf’s Chromatic Bound
Proof. If \(G\) is empty, then \(\chi(G)=0\) and \(\rho(G)=0\), so the inequality holds. Suppose \(G\) is nonempty and set \(k=\chi(G)\), so \(k\geq1\). Choose an induced vertex-critical subgraph \(H\) with \(\chi(H)=k\), as justified above. The minimum-degree lemma and the spectral lemma give, in order, $$ k-1\leq\delta(H)\leq\rho(H)\leq\rho(G). $$ The middle inequality follows because \(H\) is nonempty and its average degree is at least its minimum degree. Adding \(1\) to the first and last terms yields \(\chi(G)=k\leq1+\rho(G)\), as required. \(\square\)
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Every pair of distinct vertices is adjacent, so all four vertices need different colors and \(\chi(G)=4\). Each vertex has degree \(3\), so the all-ones vector is an eigenvector of \(\mathbf A(G)\) with eigenvalue \(3\). Also, for any eigenvalue \(\lambda\), choose an eigenvector coordinate with largest absolute value. The eigenvalue equation at that coordinate implies \(|\lambda|\leq3\), since each vertex has only three neighbors. Therefore \(\rho(G)=3\).
Wilf’s bound gives \(\chi(G)\leq1+\rho(G)=1+3=4\), and equality holds. This graph is vertex-critical: deleting any vertex leaves \(K_3\), which has chromatic number \(3<4\); its minimum degree is \(3=\chi(G)-1\).
Check: The six edges contribute \(12\) to the total degree, and \(2|E(G)|/|V(G)|=2\cdot6/4=3\), agreeing with the average degree and with \(\rho(G)=3\).
Worked Example: The Odd Cycle \(C_5\)
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\). The cycle has odd length, so it is not 2-colorable; a proper 3-coloring is \(1,2,1,2,3\) on vertices \(1,2,3,4,5\), respectively. Hence \(\chi(G)=3\). Each vertex has degree \(2\), so the all-ones vector has eigenvalue \(2\); the maximum-coordinate argument used in the previous example gives \(|\lambda|\leq2\) for every eigenvalue. Thus \(\rho(G)=2\), and the bound reads \(3\leq1+2=3\).
In fact \(C_5\) is vertex-critical: deleting any vertex leaves a path on four vertices, which can be colored alternately with two colors. Its minimum degree is \(2=\chi(G)-1\).
Check: There are \(5\) edges and \(5\) vertices, so \(2|E(G)|/|V(G)|=2\cdot5/5=2\). This equals both the minimum degree and the spectral radius.
Worked Example: A Triangle with an Isolated Vertex
Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,ca\}\). Vertices \(a,b,c\) form a triangle and \(d\) is isolated. The triangle requires three colors, and assigning any of those colors to \(d\) gives a proper coloring, so \(\chi(G)=3\). The induced subgraph \(H=G[\{a,b,c\}]\) is \(K_3\), with \(\rho(H)=2\): its all-ones vector has eigenvalue \(2\), and the maximum-coordinate bound gives no eigenvalue of absolute value greater than \(2\). The isolated vertex contributes a separate zero eigenvalue; equivalently, the same maximum-coordinate bound on \(G\), whose maximum degree is \(2\), and the eigenvalue \(2\) from \(H\), show \(\rho(G)=2\).
Wilf’s bound is \(3\leq1+2=3\). Notice that \(G\) itself is not vertex-critical: deleting the isolated vertex leaves its chromatic number unchanged. The proof uses the critical induced subgraph \(H\), not the minimum degree of all of \(G\).
Check: The degrees in \(G\) are \(2,2,2,0\), so \(\delta(G)=0\), while the three vertices of \(H\) each have degree \(2\) within \(H\). Also, \(2|E(G)|/|V(G)|=2\cdot3/4=3/2\leq2=\rho(G)\), as the spectral lemma requires.
Why the Critical Subgraph Matters
The bound comes from a chain of comparisons, not from asserting that the original graph has large minimum degree. Criticality supplies the needed degree condition in \(H\): if a vertex had fewer than \(k-1\) neighbors, at least one of \(k-1\) colors would be available for it after coloring \(H-v\). Spectral-radius monotonicity then transfers the estimate from \(H\) back to \(G\).
Common pitfall: using the minimum degree of \(G\). For the triangle-with-isolated-vertex example, the incorrect calculation would be \(k-1=3-1=2\), followed by the false claim \(2\leq\delta(G)=0\). The error is that the minimum-degree lemma applies to a vertex-critical graph, not necessarily to the original graph. The correction is to use \(H=K_3\): then \(2=k-1\leq\delta(H)=2\leq\rho(H)=2\leq\rho(G)=2\).
Wilf’s bound can be sharp, as \(K_4\) and \(C_5\) demonstrate. In other graphs the inequality may be strict; the proof guarantees an upper bound, not that the chromatic number is determined by the spectral radius alone.
Check Your Understanding
For each question, identify which graph the minimum-degree statement applies to, and use the stated spectral conventions when a graph is empty.
- Why does a graph with chromatic number \(k\geq1\) contain an induced vertex-critical subgraph with chromatic number \(k\)?
- In a vertex-critical graph with chromatic number \(k\), explain why a vertex of degree at most \(k-2\) would contradict criticality.
- State why the largest-eigenvalue assertion for an adjacency matrix is restricted to graphs with at least one vertex.
- For \(K_3\) together with one isolated vertex, compute \(\chi(G)\), \(\rho(G)\), and \(\delta(G)\). Which induced subgraph supplies the minimum-degree estimate?
- For a nonempty graph \(G\), explain how the all-ones vector gives \(2|E(G)|/|V(G)|\leq\rho(G)\).