# The chromatic number of a graph is at most its circumference

The chromatic number of a graph is at most its circumference: the length of the longest cycle in the graph. (Making an exception for forests, where the chromatic number is at most $$2$$ and the circumference is undefined.)

This can be shown as a corollary of the following theorem:

If $$G$$ has $$k$$ distinct odd cycle lengths and $$k'$$ distinct even cycle lengths, then $$\chi(G) \le k+k'+2$$. (P. Mihók, I. Schiermeyer, Cycle lengths and chromatic number of graphs, Discrete Math. 286 (2004) 147–149.)

If we assume that the longest cycle in $$G$$ has length $$\ell$$, then there are $$\ell-2$$ possible cycle lengths: $$\{3, 4, \dots, \ell-1,\ell\}$$. Therefore $$k+k'\le \ell-2$$, so by the theorem above $$\chi(G) \le \ell$$.

My question is this: does this statement have an easier proof? After all, the inequality between the chromatic number and the circumference is much weaker.

It is not hard to prove in the case $$\ell=3$$ (as seen in this recent question).

Also, there is a short argument that any graph $$G$$ with $$\chi(G)=k$$ contains a path (not a cycle) on $$k$$ vertices: let the colors be $$\{1,2,\dots,k\}$$, choose a coloring such that any vertex of color $$i$$ is adjacent to vertices $$1,2,\dots,i-1$$ (for instance, the coloring that minimizes the sum of colors over all vertices will work). Then from a vertex of color $$k$$, we can go to a vertex of color $$k-1$$, from there to a vertex of color $$k-2$$, and so on until we get to a vertex of color $$1$$.

After some more thinking, I found a simple solution. We get it very quickly from two results which are well-known in graph theory, though for completeness I will include their proofs.

Lemma 1. A graph $$G$$ with minimum degree $$k$$ contains a cycle of length at least $$k+1$$.

Proof. Take the longest path $$v_0, v_1, v_2, \dots, v_\ell$$ in $$G$$. The vertex $$v_0$$ has at least $$k$$ neighbors, and all of them must be other vertices on the path, because otherwise we could extend the path and make it even longer. The last of $$v_0$$'s neighbors on the path must be at least as far as $$v_k$$ (since there's $$k$$ of them), so we get a cycle of length at least $$k+1$$ by following the path from $$v_0$$ to $$v_0$$'s last neighbor, then taking the edge back to $$v_0$$.

Conversely, if the longest cycle in a graph $$G$$ has length $$k$$, then it has a vertex of degree $$k-1$$ or less. What's more, in every subgraph $$H$$ of $$G$$, the longest cycle has length $$k$$ or less (if it's a cycle in $$H$$, it's a cycle in $$G$$, too). So $$H$$ must have a vertex of degree $$k-1$$ or less.

A graph with this property - every subgraph has a vertex of degree $$k-1$$ or less - is called $$(k-1)$$-degenerate.

Lemma 2. A $$(k-1)$$-degenerate graph $$G$$ has chromatic number at most $$k$$.

Proof. We induct on the number of vertices in $$G$$. When $$G$$ has $$k$$ vertices or fewer, we can $$k$$-color $$G$$ by giving all the vertices different colors.

Otherwise, let $$v$$ be a vertex of degree $$k-1$$ or less. $$G-v$$ is also $$(k-1)$$-degenerate (every subgraph of $$G-v$$ is a subgraph of $$G$$) and has one fewer vertex, so by induction $$G-v$$ is $$k$$-colorable. We can $$k$$-color $$G$$ by starting with the $$k$$-coloring of $$G-v$$, then giving $$v$$ a color distinct from the colors on its neighbors (which eliminates at most $$k-1$$ options).

Putting together the two lemmas: a graph with circumference $$k$$ is $$(k-1)$$-degenerate, so it has chromatic number at most $$k$$. The chromatic number is at most the circumference.