\documentclass[11pt]{amsart} \usepackage[letterpaper,hmargin=1in,vmargin=0.92in,headheight=14pt]{geometry} \usepackage{amsmath,amssymb} \usepackage[hidelinks]{hyperref} \emergencystretch=2em \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\N}{\mathbb N} \newcommand{\Prob}{\mathbb P} \title[A counterexample to Erd\H{o}s problem 108]{A counterexample to Erd\H{o}s problem 108 via arc graphs} \author{Jensen Kohlmeyer} \address{Purdue University, West Lafayette, Indiana, USA} \email{jenwin@purdue.edu} \author{Liam Kruer} \address{Purdue University, West Lafayette, Indiana, USA} \email{kruerl@purdue.edu} \date{September 15, 2026} \subjclass[2020]{Primary 05C15; Secondary 05C38, 05C80} \keywords{Erd\H{o}s--Hajnal conjecture, chromatic number, girth, arc graph, shift graph, probabilistic method, Lean formalization} \begin{document} \begin{abstract} For every positive integer \(M\), we construct a finite triangle-free graph \(G\) with \(\chi(G)\ge M\) such that every ordinary subgraph of \(G\) containing no four-cycle is 6-colorable. Consequently, no chromatic threshold forces a subgraph of girth at least five and chromatic number at least seven. This gives a negative answer to Erd\H{o}s problem 108. The proof combines two ingredients. First, a four-cycle-free subgraph of an arc graph can be partitioned into a part controlled by a bounded-degree subgraph of the underlying graph and a forest. Second, a multipartite random construction gives graphs of large chromatic number for which every bounded-degree subgraph is 4-colorable, while retaining an acyclic orientation whose outdegree bound is independent of the prescribed degree cap. We give explicit integer part sizes and finite probability estimates. The accompanying Lean proof verifies the negative answer to the pinned Formal Conjectures statement using the permitted standard axioms. The written proof includes the triangle-free strengthening. \end{abstract} \maketitle \section{Introduction} The high-girth subgraph problem of Erd\H{o}s and Hajnal asks whether, for every pair of integers \(r\ge4\) and \(k\ge2\), there is an integer \(f(k,r)\) such that every graph of chromatic number at least \(f(k,r)\) contains a subgraph of girth at least \(r\) and chromatic number at least \(k\). The question appears as Problem 108 in Bloom's catalogue \cite{bloom} and is formalized in the Formal Conjectures library \cite{fc}. Throughout this paper, a subgraph may be obtained by deleting vertices and edges. A four-cycle-free graph excludes a copy of \(C_4\) as an ordinary subgraph. A four-cycle with chords is still forbidden. \begin{theorem}\label{thm:main} For every integer \(M\ge1\), there is a finite nonempty triangle-free simple graph \(G\) such that \(\chi(G)\ge M\) and every four-cycle-free subgraph \(H\) of \(G\) satisfies \(\chi(H)\le6\). \end{theorem} \begin{corollary}\label{cor:negative} There is no integer \(f\) such that every graph of chromatic number at least \(f\) contains a subgraph of girth at least five and chromatic number at least seven. In particular, the assertion in Erd\H{o}s problem 108 is false. \end{corollary} \begin{proof} Given a proposed threshold \(f\), apply Theorem~\ref{thm:main} with \(M=\max\{1,f\}\). Every subgraph of girth at least five is four-cycle-free, so its chromatic number is at most six. \end{proof} The construction starts with the multipartite random model used by Janzer, Steiner and Sudakov in their work on chromatic number and regular subgraphs \cite{jss}. We adapt its separated-part-size method to obtain a statement with two independent parameters, a chromatic parameter \(q\) and a degree cap \(K\). The outdegree bound depends only on \(q\). This permits us to choose \(K\) after fixing that bound and then apply an arc-graph argument. All estimates needed for this adaptation are proved here. Section 2 gives the arc-graph lemmas. Section 3 constructs the base graph, including the size estimates and both probability bounds. Section 4 proves Theorem~\ref{thm:main}. Section 5 describes the formal proof and its verification records. \paragraph{Notation.} All graphs used in the construction are finite and simple. We write \(e_F(X)\) for the number of edges in \(F[X]\), and \(e_F(X,Y)\) for the number of edges between disjoint vertex sets \(X\) and \(Y\). The maximum degree of a graph is denoted by \(\Delta\). A graph is 3-degenerate if every nonempty subgraph has a vertex of degree at most three. Such a graph is 4-colorable. For an acyclic digraph \(D\), let \(U(D)\) be its underlying undirected graph. Forests have infinite girth in the written proof. \section{Arc graphs and bounded-degree selections} \begin{definition} Let \(D\) be an acyclic orientation of a simple graph. Its arc graph \(L(D)\) has the arcs of \(D\) as vertices, with two vertices adjacent precisely when the corresponding arcs concatenate. Thus \((u,v)\) and \((v,w)\) are adjacent. We orient this edge from \((u,v)\) to \((v,w)\). \end{definition} Fix a topological ordering of \(D\). Along every oriented edge of \(L(D)\), the tail of the corresponding arc strictly increases in this ordering. The displayed orientation of \(L(D)\) is therefore acyclic. \begin{lemma}\label{lem:triangle} The graph \(L(D)\) is triangle-free. \end{lemma} \begin{proof} An acyclic orientation of a triangle has vertices \(a,b,c\) with edges \(a\to b\), \(b\to c\) and \(a\to c\). If \(a=(u,v)\) and \(b=(v,w)\), the edge \(b\to c\) makes the tail of \(c\) equal to \(w\), whereas \(a\to c\) makes it equal to \(v\). Hence \(v=w\), contradicting the fact that \(b\) is an arc of a simple graph. \end{proof} \begin{lemma}\label{lem:lift} If \(L(D)\) is \(t\)-colorable, then \(U(D)\) is \(2^t\)-colorable. In particular, \begin{equation} \chi(U(D))\le2^{\chi(L(D))}. \end{equation} \end{lemma} \begin{proof} Fix a proper coloring of \(L(D)\) with colors in \(\{1,\ldots,t\}\). Assign to each vertex \(v\) of \(D\) the set of colors occurring on arcs directed out of \(v\). If \((u,v)\) has color \(c\), the set at \(u\) contains \(c\). Every arc directed out of \(v\) is adjacent to \((u,v)\), so the set at \(v\) excludes \(c\). Adjacent vertices of \(U(D)\) therefore receive distinct subsets of the \(t\)-element color set. \end{proof} \begin{lemma}[Arc selection]\label{lem:selection} Suppose that \(D\) is acyclic, has maximum outdegree at most \(d\), and every subgraph of \(U(D)\) with maximum degree at most \begin{equation} K_d=d+\binom d2 \end{equation} is \(a\)-colorable. Then every four-cycle-free subgraph of \(L(D)\) is \((a+2)\)-colorable. \end{lemma} \begin{proof} Let \(H\subseteq L(D)\) be four-cycle-free, and restrict the natural orientation to \(H\). Partition its vertex set into \(S\) and \(T\), where \(S\) consists of the arc vertices having at least two outgoing neighbors in \(H\), and \(T\) consists of the remaining arc vertices. Fix a vertex \(v\) of \(D\). For every incoming arc \((u,v)\) belonging to \(S\), choose an unordered pair of its outgoing neighbors in \(H\). These neighbors are arcs of the form \((v,w)\). Two distinct incoming arcs cannot receive the same pair, since the two incoming arcs and the two chosen outgoing arcs would form a four-cycle. Consequently at most \[ \binom{d_D^+(v)}2\le\binom d2 \] incoming arcs at \(v\) belong to \(S\). Let \(D_S\) retain precisely the arcs of \(D\) corresponding to vertices in \(S\). Its outdegrees are at most \(d\) and its indegrees are at most \(\binom d2\). Hence \(\Delta(U(D_S))\le K_d\). By hypothesis there is a proper \(a\)-coloring \(c\) of \(U(D_S)\). Color an arc vertex \((u,v)\in S\) by \(c(u)\). If \((u,v)\) and \((v,w)\) are adjacent in \(H[S]\), the edge \(uv\) belongs to \(U(D_S)\), so these two arc vertices receive different colors. The inherited orientation of \(H[T]\) is acyclic and every vertex has outdegree at most one. Such a graph is a forest. In an acyclic orientation any undirected cycle has a source on that cycle and therefore a vertex with two outgoing edges. Color \(H[T]\) with two colors disjoint from the first palette. This gives an \((a+2)\)-coloring of \(H\). \end{proof} \begin{remark} The partition and the selected graph \(D_S\) depend on the edge-deleted subgraph \(H\). The argument works for ordinary subgraphs. The indegree bound applies to the selected digraph \(D_S\). \end{remark} \section{The multipartite base graph} \begin{theorem}\label{thm:base} For every pair of integers \(q\ge2\) and \(K\ge4\), there is a finite simple graph \(F\) with an acyclic orientation \(D\) such that \begin{enumerate} \item \(\chi(F)>2q\), \item the maximum outdegree of \(D\) is at most \(64q^2-1\), and \item every subgraph \(J\subseteq F\) with \(\Delta(J)\le K\) is 3-degenerate, and hence 4-colorable. \end{enumerate} In particular, the outdegree bound in (2) is independent of \(K\). \end{theorem} \subsection{The random model and explicit sizes} Put \begin{equation} C=64q^2,\qquad h=2(K+1),\qquad A=16CK(K+1),\qquad b=h+2. \end{equation} Choose the positive integer \(R\), then define \(B\) and the part sizes by \begin{align} R&=(16C)^h3^{2h+1}A+3A+8C+2,\label{eq:r}\\ B&=b^{C+1},\qquad n_i=R^{B-b^{i+1}}\quad(0\le ii\), independently choose a uniformly distributed vertex \(w(v,j)\in V_j\) and insert the edge \(vw(v,j)\). Orient each edge from its earlier part to its later part. This orientation is acyclic and has maximum outdegree at most \(C-1\). Write \(N=\sum_i n_i\) and \(N_0=R^B\). The following elementary estimates are the reason for the choice of exponents. \begin{lemma}\label{lem:sizes} The sizes in \eqref{eq:parts} satisfy \begin{align} n_i&\ge R\ge8C,\qquad Rn_j\le n_i\quad(ii}n_j&\le n_i,\qquad \sum_{j\ge i}n_j\le2n_i.\label{eq:tail} \end{align} For \(1\le i1\) and \(ii\), so \(R\sum_{j>i}n_j\le Cn_i\le Rn_i\), proving \eqref{eq:tail}. Fix \(i\ge1\). Since \(R\ge3A\), the successive-size inequality gives \(3x\le3An_i\le Rn_i\le n_{i-1}=L\). Next, the identity \(b=h+2\) gives \[ (h+1)(B-b^i)-hB-(B-b^{i+1})=b^i. \] Thus \(L^{h+1}=R^{b^i}N_0^h n_i\ge RN_0^h n_i\). It follows that \[ \frac{3^{2h+1}N_0^h x}{L^{h+1}}\le \frac{3^{2h+1}A}{R}\le(16C)^{-h}, \] where the last inequality is immediate from \eqref{eq:r}. \end{proof} \subsection{The deterministic cut} Consider the following local sparsity condition on a realization of \(F\): \begin{equation}\label{eq:cut} X\subseteq V_0\cup\cdots\cup V_{i-1},\quad 0<|X|\le An_i \quad\Longrightarrow\quad e_F(X)<(1+1/h)|X|. \end{equation} For \(i=0\) the condition is vacuous. \begin{lemma}\label{lem:cut} If \eqref{eq:cut} holds for every \(i\), then every subgraph of \(F\) with maximum degree at most \(K\) is 3-degenerate. \end{lemma} \begin{proof} Suppose that \(J\subseteq F\) has minimum degree at least four and maximum degree at most \(K\), and let \(s=|V(J)|>0\). By \eqref{eq:total}, there is an index \(i\) with \(s\le An_i\). Choose the largest such index. Partition \(V(J)\) into \(X,Y,Z\), according as the part index is less than, equal to, or greater than \(i\). If \(i=C-1\), then \(Z=\varnothing\). Otherwise, maximality gives \(An_{i+1} \left(2-\frac{K}{K+1}-\frac1{8(K+1)}\right)s\\ &=\left(1+\frac7{8(K+1)}\right)s>(1+1/h)|X|.\notag \end{align} In particular \(X\) is nonempty, and \(|X|\le s\le An_i\). Since \(e_J(X)\le e_F(X)\), this contradicts \eqref{eq:cut}. Thus there is no subgraph with all degrees between four and \(K\). Every subgraph of a graph of maximum degree at most \(K\) still has maximum degree at most \(K\), so every such graph is 3-degenerate. \end{proof} \subsection{The probability of a dense earlier set} \begin{lemma}\label{lem:dense} The probability that \eqref{eq:cut} fails for some \(i\) is at most \(1/8\). \end{lemma} \begin{proof} Fix \(i\ge1\) and \(1\le x\le An_i\), and put \(L=n_{i-1}\), \(m=\lceil(1+1/h)x\rceil\), and \(\delta=1/(16C)\). For a specified collection of \(m\) distinct possible edges among the earlier parts, either two edges demand different choices from the same pair \((v,j)\), in which case the event is impossible, or they impose \(m\) independent choices. Every target part has size at least \(L\), so the probability that all the specified edges occur is at most \(L^{-m}\). There are at most \(\binom{N_0}{x}\) possible sets \(X\) of size \(x\), and at most \(\binom{x^2}{m}\) choices of the required edges. Thus the probability that an earlier set of size \(x\) violates \eqref{eq:cut} is at most \begin{equation}\label{eq:union} \binom{N_0}{x}\binom{x^2}{m}L^{-m}\le \left(\frac{3N_0}{x}\right)^x\left(\frac{3x}{L}\right)^m. \end{equation} Here we used \(\binom nk\le(en/k)^k\le(3n/k)^k\) for \(k\ge1\), together with \(m\ge x\). If the prescribed number of edges is impossible, the same estimate holds with probability zero. Set \(a=3N_0/x\) and \(z=3x/L\). By Lemma~\ref{lem:sizes}, \(0i}p_j(I)>\frac{C}{4q}-1=16q-1\ge15q. \end{equation} The part of \(I\) in indices at least \(i\) is still independent and preserves both inequalities. We may therefore count only sets in this suffix. Fix a suffix set \(I\) satisfying these inequalities, and put \(t=|I\cap V_i|\ge n_i/(4q)\). For \(I\) to be independent, all choices from its \(t\) vertices in \(V_i\) to each later part \(V_j\) must avoid \(I\cap V_j\). These choices are independent, so \begin{equation}\label{eq:heavyprob} \Prob(I\text{ is independent})\le\prod_{j>i}(1-p_j(I))^t \le\exp\left(-t\sum_{j>i}p_j(I)\right)\le e^{-3n_i}. \end{equation} Indeed, \eqref{eq:heavy} and \(t\ge n_i/(4q)\) give an exponent of absolute value at least \(15n_i/4\). By \eqref{eq:tail}, the entire suffix has at most \(2n_i\) vertices. There are therefore at most \(2^{2n_i}\le e^{2n_i}\) possible suffix sets. The union bound and \eqref{eq:heavyprob} give probability at most \(e^{-n_i}\) for a witness with a fixed first heavy index \(i\). Finally, \(n_i\ge8C\) and \(e^{n_i}\ge1+n_i\) imply \(e^{-n_i}\le1/(8C)\). Summing over all \(i\) proves the lemma. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:base}] Lemmas~\ref{lem:dense} and \ref{lem:heavy} bound the two failure probabilities by \(1/8\) each. Their sum is less than one, so there is a realization satisfying \eqref{eq:cut} in which every independent set has weight less than \(C/(2q)\). Lemma~\ref{lem:cut} proves (3), and the orientation of the construction proves (2). If \(F\) were \(2q\)-colorable, its color classes would be independent sets of total weight strictly less than \(2q\cdot C/(2q)=C\). But the color classes partition a vertex set of weight \(C\). This contradiction proves \(\chi(F)>2q\), completing (1). \end{proof} \section{Proof of the main theorem} \begin{proof}[Proof of Theorem~\ref{thm:main}] Fix \(M\ge1\) and put \begin{equation} q=2^M+2,\qquad C=64q^2,\qquad d=C-1,\qquad K=d+\binom d2. \end{equation} These parameters satisfy \(q\ge2\) and \(K\ge4\). Apply Theorem~\ref{thm:base} with this pair \((q,K)\) to obtain \(F=U(D)\). Every subgraph of \(F\) with maximum degree at most \(K\) is 4-colorable, and the maximum outdegree of \(D\) is at most \(d\). The choice of \(K\) is legitimate because the outdegree bound in Theorem~\ref{thm:base} is independent of \(K\). Set \(G=L(D)\). Lemma~\ref{lem:selection}, with \(a=4\), shows that every four-cycle-free subgraph of \(G\) is 6-colorable. Lemma~\ref{lem:triangle} shows that \(G\) is triangle-free. If \(\chi(G)\le M\), then Lemma~\ref{lem:lift} gives \[ \chi(F)\le 2^{\chi(G)}\le2^M<2q, \] contrary to Theorem~\ref{thm:base}. Thus \(\chi(G)>M\). The graph \(G\) is finite, and this inequality also ensures that it is nonempty. \end{proof} \begin{remark} List the vertices of \(D\) in a topological order. The map sending an arc to the ordered pair of its endpoint indices identifies \(L(D)\) with an induced subgraph of the canonical shift graph on ordered pairs \((i,j)\) with \(i