Why Criticality Controls Degree
The chromatic number describes how many colors are needed for the whole graph. By itself, it does not say that every vertex has many neighbors: a graph can contain a highly chromatic part alongside a vertex of very small degree. The minimum-degree bound in this tutorial applies when the graph is critical in a specific sense: deleting any one vertex must lower the chromatic number. This condition lets us color the rest of the graph with fewer colors and then ask whether the deleted vertex can be added back.
All graphs here are finite and simple. A proper coloring assigns colors to vertices so that adjacent vertices have different colors. The chromatic number \(\chi(G)\) is the minimum number of colors in a proper coloring of \(G\). We use \(\chi(G)=0\) for the graph with no vertices; a nonempty graph with no edges has chromatic number \(1\). The degree \(\deg(v)\) is the number of neighbors of \(v\), and \(\delta(G)\) is the minimum degree among the vertices of a nonempty graph.
The deletion condition is essential: it says that each vertex matters to the chromatic number. It is a condition about deleting vertices, not just a statement that the graph has chromatic number \(k\). When \(k=1\), the only vertex-critical \(1\)-chromatic graph is the single-vertex graph: it has degree \(0\), so the bound \(\delta(G)\ge k-1\) holds. We focus below on \(k\ge2\), where the bound has substantive content.
The Minimum-Degree Bound
Proof. Fix a vertex \(v\). By vertex-criticality, \(\chi(G-v)<k\), so \(G-v\) has a proper coloring using colors from a palette of \(k-1\) colors. Suppose, for contradiction, that \(\deg(v)\le k-2\). The neighbors of \(v\) can then use at most \(k-2\) distinct colors, since there are at most \(k-2\) neighbors. At least one of the \(k-1\) colors in the palette is absent from those neighbors. Assign that color to \(v\). Every edge not incident with \(v\) remains properly colored, and every edge incident with \(v\) joins \(v\) to a neighbor of a different color. This gives a proper coloring of \(G\) with \(k-1\) colors, contradicting \(\chi(G)=k\). Thus \(\deg(v)\ge k-1\). Since this holds for every vertex, the minimum degree also satisfies \(\delta(G)\ge k-1\). \(\square\)
The proof works by extending a coloring across one deleted vertex. The degree bound ensures that the neighbors cannot block every color in the palette. Criticality supplies the coloring of \(G-v\); without that hypothesis, the extension argument has no reason to start with a coloring using only \(k-1\) colors.
Proof. Since \(S\) is a proper subset, choose a vertex \(v\in V(G)\setminus S\). Every vertex and edge of \(G[S]\) is also present in \(G-v\), so \(G[S]\) is a subgraph of \(G-v\). By vertex-criticality, \(G-v\) has a proper coloring using at most \(k-1\) colors. Restrict that coloring to \(S\); deleting vertices cannot create an edge whose endpoints have the same color. Therefore \(G[S]\) has a proper coloring with at most \(k-1\) colors. If \(S\) is empty, its chromatic number is \(0\), which also satisfies the claim. \(\square\)
This proposition concerns induced subgraphs on fewer vertices. It does not assert that every spanning subgraph formed by deleting edges has lower chromatic number: such a graph can keep all the vertices and retain the same chromatic requirement.
Worked Examples
Worked Example: The Complete Graph \(K_4\)
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24,34\}\). Verify that \(G\) is vertex-critical \(4\)-chromatic and check the degree bound.
Every pair of distinct vertices is joined by an edge. Therefore a proper coloring must assign four different colors, so \(\chi(G)\ge4\). Assigning a different color to each of the four vertices gives a proper coloring, so \(\chi(G)\le4\). Together these calculations give \(\chi(G)=4\).
Deleting vertex \(1\) leaves the triangle on \(\{2,3,4\}\), which needs three different colors and can be colored with three. Deleting any other vertex leaves a triangle for the same reason: the remaining three vertices are still pairwise adjacent. Thus every one-vertex deletion has chromatic number \(3<4\), and \(G\) is vertex-critical \(4\)-chromatic.
Each vertex is adjacent to the other three, so each degree is \(3\). Hence \(\delta(G)=3\), and the bound gives \(k-1=4-1=3\). The edge count also agrees with the specified edge set: it lists \(6\) edges, and the degree sum is \(4\cdot3=12=2\cdot6\).
Check: the graph is vertex-critical, and its minimum degree equals the required lower bound \(3\).
Worked Example: A Vertex-Critical Odd Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45,51\}\). Verify that \(G\) is vertex-critical \(3\)-chromatic.
For an upper bound, color vertices \(1,3\) with color A, vertices \(2,4\) with color B, and vertex \(5\) with color C. The edges \(12,23,34,45,51\) have endpoint-color pairs A–B, B–A, A–B, B–C, and C–A, respectively. Thus this is a proper coloring using \(3\) colors.
Two colors cannot suffice: starting with vertex \(1\), the colors would have to alternate along \(12,23,34,45\). That would give vertices \(1\) and \(5\) the same color, but \(51\) is an edge. Therefore \(\chi(G)=3\).
Deleting any vertex leaves the other four vertices in a path. A path can be colored with two colors by alternating them along its edges; for example, deleting \(1\) leaves the path \(2,3,4,5\), colored B, A, B, A. The cycle has the same structure after deletion of any vertex, so every vertex deletion has chromatic number at most \(2\), which is less than \(3\). Therefore \(G\) is vertex-critical \(3\)-chromatic.
Each vertex has two neighbors: the edge list gives the pairs \(12,23,34,45,51\), with exactly two incident edges at each vertex. Hence \(\delta(G)=2\), matching \(k-1=3-1=2\). As a count check, the list has \(5\) edges and the degree sum is \(5\cdot2=10=2\cdot5\).
Check: the coloring shows \(\chi(G)\le3\), the alternating-color contradiction shows \(\chi(G)\ge3\), and every vertex deletion admits a two-coloring.
Worked Example: A Low-Degree Vertex Without Criticality
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,13,14,23,24,34,15\}\). The vertices \(1,2,3,4\) form a \(K_4\), and vertex \(5\) is adjacent only to vertex \(1\). Compare \(\chi(G)\) and \(\delta(G)\).
The four vertices \(\{1,2,3,4\}\) are pairwise adjacent, so they require four different colors; thus \(\chi(G)\ge4\). Color them A, B, C, D, respectively, and give vertex \(5\) color B. Its only neighbor is \(1\), which has color A, so this is a proper four-coloring. Therefore \(\chi(G)=4\).
The degrees are \(\deg(1)=4\), because the incident edges are \(12,13,14,15\); \(\deg(2)=3\), from \(12,23,24\); \(\deg(3)=3\), from \(13,23,34\); \(\deg(4)=3\), from \(14,24,34\); and \(\deg(5)=1\), from \(15\). Consequently \(\delta(G)=1\), while \(k-1=4-1=3\). The edge list contains \(7\) edges, and the degree sum is \(4+3+3+3+1=14=2\cdot7\).
Deleting vertex \(5\) leaves the \(K_4\), which still has chromatic number \(4\). Thus \(G\) is not vertex-critical \(4\)-chromatic. This is precisely why the theorem cannot be applied, despite the fact that \(\chi(G)=4\).
Check: the clique forces four colors, but the pendant vertex has degree \(1<3\). The example confirms that chromatic number alone does not imply the minimum-degree bound.
Criticality and Common Mistakes
The degree bound can be read as a local obstruction to extending a coloring. In a vertex-critical graph, removing any vertex leaves a graph colorable with at most \(k-1\) colors. If the removed vertex had at most \(k-2\) neighbors, those neighbors could forbid at most \(k-2\) colors. One color would remain available, contradicting the assumption that the original graph needs \(k\) colors.
A common mistake is to reverse this argument without checking its hypothesis: “The graph has chromatic number \(k\), so deleting a vertex leaves a \((k-1)\)-colorable graph.” That claim is false. In the third example, \(\chi(G)=4\), but deleting vertex \(5\) leaves \(K_4\), which still needs \(4\) colors. The correction is to use \(\chi(G-v)<k\) only when vertex-criticality has been established. Then the extension argument proves the degree bound.
The bound is necessary for vertex-criticality, not a definition of it. A minimum degree of at least \(k-1\) by itself does not guarantee that deleting every vertex lowers the chromatic number. To check criticality, verify both conditions: the graph has chromatic number \(k\), and every one-vertex deletion has chromatic number less than \(k\).
Check Your Understanding
Use the definition and the vertex-extension argument to answer the following.
- In a vertex-critical \(5\)-chromatic graph, what lower bound does the theorem give for the degree of every vertex?
- Explain why a vertex with at most \(k-2\) neighbors can be added back to a \((k-1)\)-coloring of \(G-v\).
- For the graph with edges \(12,23,34,45,51\), explain why two colors do not suffice and why deleting a vertex leaves a graph colorable with two colors.
- In the graph formed by \(K_4\) and a vertex adjacent only to vertex \(1\), which deletion shows that the graph is not vertex-critical \(4\)-chromatic?
- Does the proposition about proper induced subgraphs assert that deleting an edge from a spanning graph must lower its chromatic number? Explain.