Erdős's High-Girth, High-Chromatic Construction

The Existence Problem

Large chromatic number usually suggests that a graph has many local obstructions to coloring. A short cycle is one such obstruction, but it is a weak one: a graph can have large chromatic number without containing any cycles up to a prescribed length. Erdős's construction proves this by first selecting a random graph, then deleting a small set of vertices to remove its short cycles. The essential balance is that the graph retains many vertices while its independent sets are small.

All graphs below are finite and simple. For a graph \(G\), an independent set is a set of pairwise nonadjacent vertices, and \(\alpha(G)\) is the largest size of such a set. The chromatic number \(\chi(G)\) is the least number of colors in a proper vertex coloring. A cycle of length at most \(g\) will be called a short cycle in this tutorial. For a graph with no cycles, its girth is conventionally infinite.

We prove the theorem using the random graph \(G(n,p)\): its vertex set is \(\{1,\dots,n\}\), and each possible edge is included independently with probability \(p\). Two estimates will be needed. The first controls how many short cycles appear; the second makes large independent sets unlikely.

Two Estimates for the Random Graph

Proof. In any proper coloring, each color class is an independent set and therefore contains at most \(\alpha(G)\) vertices. If the coloring uses \(q\) colors, then \(|V(G)|\le q\alpha(G)\). This holds for every proper coloring, including one using the minimum possible number \(\chi(G)\) of colors. Dividing by the positive integer \(\alpha(G)\) gives the claimed inequality. \(\square\)

Let \(X\) count the cycles of lengths from \(3\) through \(g\) in \(G(n,p)\). For each \(i\), there are at most \(n^i/(2i)\) distinct cycles of length \(i\): an ordered list of \(i\) distinct vertices specifies a cycle, and each cycle is counted \(2i\) times by choices of starting point and direction. A specified cycle of length \(i\) appears with probability \(p^i\), since its \(i\) edges are selected independently. By summing the indicators of all these cycles,

For the independent-set estimate, let \(Y_r\) count the independent vertex sets of size \(r\). A specified \(r\)-set is independent precisely when its \(\binom r2\) possible internal edges are all absent. Thus, when \(1\le r\le n\),

Here \(\binom nr\le(en/r)^r\) and \(1-p\le e^{-p}\). If \(\alpha(G(n,p))\ge r\), then \(Y_r\ge1\); consequently, \(\Pr(\alpha(G(n,p))\ge r)\le\mathbb{E}Y_r\). This is the first-moment estimate that will control the independence number.

Proof of the Construction

Proof of the Theorem. Fix integers \(g\ge3\) and \(k\ge1\). Set \(\varepsilon=1/(2g)\), take \(n\) sufficiently large, and choose

For sufficiently large \(n\), \(0<p<1\) and \(r\le n\), because \(4\ln n/n^\varepsilon\) tends to zero. Also \(np=n^\varepsilon\). For each \(3\le i\le g\), we have \((np)^i=n^{i\varepsilon}\le n^{g\varepsilon}=\sqrt n\). The cycle estimate therefore gives

By Markov's inequality, \(\Pr(X>g\sqrt n)\le \mathbb{E}X/(g\sqrt n)\le 1/2\). Hence the event \(A=\{X\le g\sqrt n\}\) has probability at least \(1/2\).

Next, \(r-1\ge 4n^{1-\varepsilon}\ln n-1\), so \(p(r-1)\ge4\ln n-p\ge4\ln n-1\). For \(n\) large enough that \(\ln n\ge1\), this is at least \(3\ln n\). Applying the independent-set estimate and using \(r\ge1\), we obtain

When \(\ln n\ge4\), \(1-\tfrac12\ln n\le-\tfrac14\ln n\). Therefore \(\mathbb{E}Y_r\le\exp(-r\ln n/4)\), which is less than \(1/4\) for all sufficiently large \(n\). It follows that the event \(B=\{\alpha(G(n,p))<r\}\) has probability greater than \(3/4\).

No independence between \(A\) and \(B\) is needed. The union bound gives \(\Pr(A\cap B)\ge1-\Pr(A^{\mathrm c})-\Pr(B^{\mathrm c})>1-1/2-1/4=1/4\). Thus some graph \(G\) satisfies both \(X\le g\sqrt n\) and \(\alpha(G)<r\).

From this \(G\), choose one vertex on each cycle of length at most \(g\), and let \(S\) be the set of chosen vertices. If a vertex is chosen more than once, it still belongs to \(S\) only once, so \(|S|\le X\le g\sqrt n\). Let \(H=G-S\), the induced subgraph on the vertices not in \(S\). Every cycle in \(H\) would also be a cycle in \(G\); every cycle of length at most \(g\) in \(G\) has a chosen vertex in \(S\). Thus \(H\) has no cycle of length at most \(g\). Moreover, an independent set in \(H\) is also independent in \(G\), so \(\alpha(H)\le\alpha(G)<r\), while \(|V(H)|\ge n-g\sqrt n\).

Finally, \(n-g\sqrt n>kr\) for sufficiently large \(n\). Indeed, for large \(n\), \(n-g\sqrt n\ge n/2\) and \(r\le5n^{1-\varepsilon}\ln n\), so \((n-g\sqrt n)/r\ge n^\varepsilon/(10\ln n)\). This last quantity tends to infinity: writing \(t=\ln n\), \(n^\varepsilon/\ln n=e^{\varepsilon t}/t\ge \varepsilon^2t/2\), using \(e^x\ge x^2/2\) for \(x\ge0\). The chromatic lower bound now yields \(\chi(H)\ge |V(H)|/\alpha(H)>|V(H)|/r>k\). This proves the theorem. \(\square\)

Worked Examples

Why the Probability Bounds Must Be Combined Carefully

The construction does not require the short-cycle event and the small-independence event to be independent. It only requires their failure probabilities to have sum less than \(1\). The deletion step then preserves the independence-number bound because passing to an induced subgraph cannot create a new independent set that was absent from the original graph. At the same time, deleting at most \(g\sqrt n\) vertices leaves enough vertices for the ratio \(|V(H)|/\alpha(H)\) to exceed any fixed target.

Common mistake. From \(\Pr(A)\ge1/2\) and \(\Pr(B)>3/4\), one cannot multiply these probabilities and claim \(\Pr(A\cap B)>3/8\); multiplication would require independence, which has not been established. The valid calculation is the union bound: \(\Pr(A\cap B)\ge1-\Pr(A^{\mathrm c})-\Pr(B^{\mathrm c})>1-\tfrac12-\tfrac14=\tfrac14\). This positive lower bound is enough to guarantee at least one graph satisfying both properties.