\documentclass[11pt]{amsart} \usepackage[letterpaper,hmargin=1in,vmargin=.92in,headheight=14pt]{geometry} \usepackage{amsmath,amssymb,mathtools,array,longtable} \usepackage[hidelinks]{hyperref} \emergencystretch=2em \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newcommand{\Z}{\mathbb Z} \newcommand{\R}{\mathbb R} \newcommand{\classes}{\mathcal R} \newcommand{\res}[2]{[#1]_{#2}} \newcommand{\modulo}[1]{\pmod{#1}} \DeclareMathOperator{\Cay}{Cay} \title[Vertex-critical graphs with no small critical edge set]{Vertex-critical four-chromatic graphs with no small critical edge set} \author{Liam Kruer} \author{Jensen Kohlmeyer} \date{September 10, 2026. Research manuscript for review.} \subjclass[2020]{Primary 05C15; Secondary 05C25, 11A07, 68V15} \keywords{Erd\H{o}s problem 944, vertex-critical graph, critical edge set, cyclic graph, Chinese remainder theorem, Lean} \begin{document} \begin{abstract} We construct, for every positive integer $r$, a finite four-chromatic graph whose every vertex is critical, while deleting any set of at most $r$ edges leaves its chromatic number unchanged. The construction combines punctured cyclic three-colorings, an integral height character, an Andr\'asfai winding inequality, and a Chinese remainder construction with an exact classification of its small-deficit characters. Together with the established result of Skottov\'a and Steiner for five or more colors, this gives an affirmative answer to the existence statement in Erd\H{o}s problem 944. The complete existence statement for all $k\ge4$ is formalized in one Lean file with 570 proved theorems. This includes the four-color parameter construction and character argument, and the higher-color construction, local structure, and propagation proof. The exact challenge theorem is checked without admitted proof placeholders or additional axioms. \end{abstract} \maketitle \section{Introduction} An edge set of a graph is critical if deleting it lowers the chromatic number. A graph is vertex-critical if deleting any vertex lowers its chromatic number. We use the terminology $(k,r)$-graph for a finite graph $G$ satisfying \begin{equation} \chi(G)=k,\quad \chi(G-v)=k-1\quad(v\in V(G)),\quad \chi(G-E')=k\quad(E'\subseteq E(G),\ |E'|\le r).\label{eq:graph} \end{equation} The existence statement of Erd\H{o}s problem 944 asks whether a $(k,r)$-graph exists for every $k\ge4$ and $r\ge1$. It is also the statement selected by the Formal Conjectures challenge~\cite{Bloom,Formal}. Skottov\'a and Steiner~\cite[Theorem 1.3]{SkottovaSteiner} prove the existence of such graphs for every $k\ge5$ and $r\ge1$. Their result leaves the four-color case. \begin{theorem}[Construction]\label{thm:construction} For every integer $r\ge1$, there is a finite $(4,r)$-graph. \end{theorem} \begin{corollary} For every $k\ge4$ and $r\ge1$, there is a finite $(k,r)$-graph. \end{corollary} The corollary combines Theorem~\ref{thm:construction} with the cited higher-color theorem. We do not claim a bound of practical size for the number of vertices, nor the stronger assertion about the existence of graphs of every sufficiently large order. \subsection{Status of the proof and its formalization} This is a research manuscript for mathematical review. Sections~\ref{sec:criterion}--\ref{sec:words} give the four-color proof in ordinary mathematics. The accompanying Lean file proves that theorem for every natural $r$, including the recursive parameters, punctured colorings, winding argument, word construction, finite rounding, exact CRT character classification, and edge-robustness deduction. The file also formalizes the higher-color construction of Skottov\'a and Steiner and proves its required existence statement. This includes the exceptional cases $k=5,6,8$, with a paired-ring argument for even $k$ and an overlapping-interval count for $k=5$. All witnesses are transported to the universe required by the challenge. The theorem \texttt{Bounty.target} proves exactly the displayed proposition for every $k\ge4$ and $r\ge1$. Section~\ref{sec:lean} gives the proof correspondence and pinned verification environment. The symbolic proof is independent of the supplementary finite computations. \subsection{Notation} For an integer $x$ and a positive integer $n$, write $\res xn$ for the least nonnegative residue of $x$ modulo $n$. We identify elements of $\Z/n\Z$ with their least representatives when inequalities or residues modulo $3$ are used. A direction pair is an unordered pair $\{s,-s\}$ in $\Z/n\Z$. If $S$ is an inverse-closed set of nonzero directions, $\Cay(\Z/n\Z,S)$ has the edges $\{v,v+s\}$ for $s\in S$. An edge is bad for a coloring when its endpoints receive the same color. All edge counts below count distinct undirected edges. \section{A cyclic graph construction criterion}\label{sec:criterion} Suppose that $n\equiv1\modulo3$ and put \begin{equation} N_n=\{1,n-1\}\cup\{s:00$ for some $i$. \end{enumerate} Start with $H=\Cay(\Z/n\Z,S)$. For each $i$, and every vertex $x$ with $x\equiv i\modulo q$, add the edges \begin{equation} \{x+ja_i,x+(j+\ell)a_i\},\qquad \ell\in\{4,7,\ldots,q\},\quad 0\le j\le q-\ell.\label{eq:chords} \end{equation} Identify repeated edges. The resulting simple graph $G$ is a $(4,r)$-graph. \end{theorem} \subsection{Punctured colorings} Delete a vertex $v$, let $i=\res vq$, and color every remaining vertex by \begin{equation} c_v(u)=\res{\res{a_i^{-1}(u-v)}n}3\qquad(u\ne v).\label{eq:puncture} \end{equation} If a normalized difference is $2$ modulo $3$, its color difference is $2$ without a wrap and $1$ with a wrap, since $n\equiv1\modulo3$. Differences $1$ and $-1$ are also proper after coordinate zero is deleted. Condition (i) therefore makes every core edge proper. For a chord of type $i$, the normalized forward length is $1$ modulo $3$. The chord lies inside a $q$-step gap between consecutive vertices whose residue modulo $q$ is $i$. Such a gap has no vertex of that residue class in its interior because $a_i$ remains a unit modulo $q$. The puncture $v$ consequently cannot lie strictly inside the chord's forward arc. If it is an endpoint, the edge has been deleted. Otherwise there is no wrap and the color difference is $1$ modulo $3$. Chords of any other type are proper by Condition (ii). Thus $G-v$ is three-colorable for every $v$, and assigning one new color to $v$ shows that $\chi(G)\le4$. \subsection{Height characters} For different colors $b,c\in\Z/3\Z$, let $\sigma(b,c)$ be the unique element of $\{-1,1\}$ congruent to $c-b$ modulo $3$. \begin{lemma}[Height character]\label{lem:height} Let $U$ be an inverse-closed set of directions generating $\Z/n\Z$, and suppose its Cayley graph is properly three-colored. There is a character $K\in\Z/n\Z$ and a translation-invariant mean height increment $\theta_u$ for every oriented generator, satisfying \begin{equation} |\theta_u|\le1,\qquad \theta_u\equiv3+\frac{6Ku}{n}\modulo6.\label{eq:theta} \end{equation} The height increment along a fixed word depends only on its starting group vertex. Its mean is the signed sum of the generator means. In particular, an odd word with endpoint displacement $s$ has mean congruent to $3+6Ks/n$ modulo $6$. \end{lemma} \begin{proof} Choose representatives $u_1,\ldots,u_d$ for the generator pairs and pull the coloring back under the map $\Z^d\to\Z/n\Z$ taking $e_j$ to $u_j$. Give each oriented grid edge the increment $\sigma$ of its endpoint colors. The sum around a square is even, divisible by $3$, and between $-4$ and $4$. It is therefore zero. Backtracks also have zero sum. Commuting adjacent coordinate steps and cancelling backtracks reduces every closed grid walk, so the increments integrate to an integer height $h$ on $\Z^d$. Write $\Lambda$ for the kernel of the map. For $\lambda\in\Lambda$, the difference $h(x+\lambda)-h(x)$ is divisible by $3$. Its change when $x$ moves by a unit grid step is in $\{-2,0,2\}$ and divisible by $3$, so that difference is independent of $x$. Denote it by $\phi(\lambda)$. It is additive in $\lambda$ and extends to a real linear functional $\theta\cdot x$, since $\Lambda$ has finite index. The period $ne_j$ gives $|\theta_j|\le1$. Height parity and color congruence give \[ \phi(\lambda)\equiv\sum_j\lambda_j\modulo2,\qquad \phi(\lambda)\equiv0\modulo3. \] Hence $(\theta-3\mathbf 1)/6$ takes integral values on $\Lambda$. Modulo integral functionals it factors through a character of the cyclic quotient, proving \eqref{eq:theta}. Changing a lift of a starting vertex adds the same period constant to both heights defining a word increment. The increment is therefore well-defined. For a single generator, summing over an orbit gives its period height, so its average increment is $\theta_j$. Translation permutes the starting vertices, and therefore averaging a word adds the signed generator means. The contribution of the constant $3$ is $3$ modulo $6$ for an odd word. \end{proof} \subsection{Bad edges and the deficit bound} Suppose a three-coloring of $G$ has at most $r$ bad edges. A direction pair in $S$ is called bad if at least one of its translated edges is bad. There are at most $r$ such pairs, since different direction pairs have disjoint edge sets. As $q>r$, one of the chosen unit directions has no bad edge. The remaining proper directions still generate $\Z/n\Z$. If a target direction $s$ is bad, its $r$ words in Condition (iii) avoid its own pair. At most $r-1$ other bad pairs can spoil these mutually disjoint words, so at least one is wholly proper. If $s$ is proper, use the word $(s,s,-s)$ instead. Apply Lemma~\ref{lem:height} to the proper directions and let $\delta_s(v)$ be the height increment of a selected three-step word for $s$, starting at $v$. It belongs to $\{-3,-1,1,3\}$ and has the endpoint color difference as its residue modulo $3$. Consequently it is $\pm1$ at a proper $s$-edge and $\pm3$ at a bad one. If $\beta_s$ is the number of bad $s$-edges and $\theta_s$ is the mean of these word increments, then \begin{equation} \theta_s\equiv3+\frac{6Ks}{n}\modulo6,\qquad |\theta_s|\le1+\frac{2\beta_s}{n}.\label{eq:badbound} \end{equation} There are exactly $n$ edges in this direction pair: the assumption that $s$ is not an involution makes $v\mapsto\{v,v+s\}$ injective. If $x=\res{Ks}n/n$, the least possible absolute value of a real number congruent to $3+6x$ modulo $6$ is $3-6\min(x,1-x)$. Equation \eqref{eq:badbound} gives $\beta_s\ge D_K(s)$. Summing over the representatives in $J$ therefore proves \begin{equation} F(K)\le\sum_{s\in J}\beta_s\le r.\label{eq:fbound} \end{equation} Moreover, $D_K(s)>0$ forces $|\theta_s|>1$. \subsection{The winding inequality} Let $B_t$ have vertex set $\{0,\ldots,3t+1\}$ and an edge $ij$, with $i0$ and there are no bad cycle edges, then $C\le3t+2$. Its parity agrees with $3t+2$ and it is divisible by $3$, giving $C\le3t$. Otherwise let $b$ be the number of bad cycle edges, so $1\le b\le t$. The $3t+2-b>2b$ proper edges imply that some bad cycle edge is followed by at least three proper edges before the next bad one. Rotate this four-edge window to the start and delete its three interior vertices. Rotation preserves $B_t$, since $3t+2\equiv2\modulo3$ and reversing an allowed cyclic difference again gives a difference $1$ modulo $3$. The remaining induced graph, in its cyclic order, is $B_{t-1}$. At least the initial bad edge disappears. If $s\in\{-3,-1,1,3\}$ is the sum of the following three proper increments, the four removed increments sum to $3+s$. The maximal increment on the new bridge is, respectively, $3,-1,1,3$. Thus the old cycle sum is at most the new one plus $3$. Induction proves $C\le3t$. The maximal path increments dominate the assigned increments. The closing increment is at least $-1$, so a path sum exceeding $3t+1$ would give $C>3t$. This proves the upper bound. Reverse the path and negate its increments to obtain the lower bound. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:criterion}] The punctured colorings prove the vertex-deletion assertions and $\chi(G)\le4$. If a three-coloring had at most $r$ bad edges, \eqref{eq:fbound} and Condition (iv) would supply an $a_i$ with $|\theta_{a_i}|>1$. Reverse the orientation if necessary. The sum of its word increments around its unit Hamiltonian cycle then exceeds $n$. Partition the cycle into its $n/q$ designated gaps of length $q=3t+1$. Some gap has sum exceeding $q$. Its vertices span $B_t$ by \eqref{eq:chords} and the unit core edges, contradicting Lemma~\ref{lem:winding}, since the entire graph has at most $r\le t$ bad edges. Reversal preserves the same gap graphs. Thus every three-coloring of $G$ has more than $r$ bad edges. In particular $G$ is not three-colorable, so $\chi(G)=4$. A three-coloring after deleting at most $r$ edges would have at most $r$ bad edges in $G$, which is impossible. Finally, $\chi(G-v)$ cannot be at most $2$, since adding $v$ in a new color would three-color $G$. Therefore \eqref{eq:graph} holds with $k=4$. \end{proof} \section{The integer parameter construction} Fix $r\ge1$. Choose $t=r$ unless $5\mid 3r+1$, in which case choose $t=r+1$. Then $q=3t+1$ is coprime to $15$. Put \begin{equation} D=30q,\qquad M=150q=5D,\qquad a_0=1.\label{eq:DM} \end{equation} For $1\le j10qa_{j-1},\label{eq:separate}\\ d_j\equiv\kappa_i^{-1}\modulo{d_i}\qquad(1\le i1000(r+1)qL^2.\label{eq:nlarge} \end{gather} Such integers form a nonempty progression of step $qL$. To see this, separate the common factor $5$ of the $a_j$. Their prescribed residues are all $-1$ modulo $5$, because $\kappa_j\equiv1\modulo5$. The remaining moduli $d_j$ are pairwise coprime and coprime to $3q$, while $q$ is coprime to $15$. The Chinese remainder theorem therefore applies to $3,q,5,d_1,\ldots,d_{q-1}$, and an arbitrarily large member may be chosen. For a deterministic choice, take the least member satisfying \eqref{eq:nlarge}. Each $a_j$ is a unit modulo $n$, and its least positive inverse for $j\ge1$ is \begin{equation} \res{a_j^{-1}}n=\frac{1+\kappa_jn}{a_j}.\label{eq:inverse} \end{equation} The numerator is divisible by $a_j$ by \eqref{eq:n2}. Since $0<\kappa_j0$ and set $\ell=\res{a_i\kappa_j}{a_j}$. Equation \eqref{eq:inverse} gives the integer representative \begin{equation} R_{ij}=\frac{a_i+\ell n}{a_j}.\label{eq:rij} \end{equation} We check that it is less than $n/q$, which also confirms that it is the least positive representative. If $i=0$, then $\ell=\kappa_j$, and $\ell/a_j<1/(4q)$. If $i>j\ge1$, condition \eqref{eq:disjointmod} gives $\ell=5$, again with $\ell/a_j<1/(4q)$. If $00$, $i\ne j$. For $i=0$ we instead have $\ell\equiv0\modulo3$. Using $a_j\equiv2\modulo3$ and $n\equiv1\modulo3$ in \eqref{eq:rij} now gives $R_{ij}\equiv2\modulo3$ in every case. Since $a_i\le P=L/3$, the bound on $n$ implies $n>4q\max_i a_i$. Equation \eqref{eq:rij} consequently gives $00$. This proves \eqref{eq:ratios}. Equality $a_i=a_j$ modulo $n$ would make their ratio $1$, while $a_i=-a_j$ would make it $n-1$. Neither has residue $2$ modulo $3$. \end{proof} \section{The core and its periodic residue classes}\label{sec:core} Define \begin{equation} S=\left(\bigcap_{i=0}^{q-1}a_iN_n\right)\setminus\{n/2\},\label{eq:S} \end{equation} where the last removal is made only when $n$ is even. The set $N_n$ is inverse-closed because the negative of a residue $2$ modulo $3$ has the same residue, since $n\equiv1\modulo3$. Thus $S$ is inverse-closed and has no involution. Lemma~\ref{lem:ratios} puts all $\pm a_i$ in $S$. It proves Conditions (i) and (ii) as well. For $\ell\le q$ with $\ell\equiv1\modulo3$, the product of $\ell$ with an off-diagonal ratio is less than $n$ and is $2$ modulo $3$. For $1\le j0).\label{eq:blocksize} \end{equation} To check this, use $\kappa_j\equiv1\modulo5$, so that $e_j(s)$ and $s$ have the same residue modulo $5$. The residue $2$ modulo $3$ fixes the least representative modulo $15$ as $2+3h$. Since $d_j\equiv1\modulo{15}$, listing these representatives in $[0,5d_j)$ gives exactly \eqref{eq:blocksize}. The $e_j$ coordinates modulo $d_j$, together with the residues modulo $3$ and $5$, are independent CRT coordinates. Every block is nonempty, so in particular $\classes$ contains more than one class. \section{Exact character rigidity} Let $B=[1/3,2/3]\subseteq\R/\Z$. The following lemma is the arithmetic classification on which the construction rests. \begin{lemma}[Rigidity of the periodic part]\label{lem:rigidity} Suppose $\alpha\in L^{-1}\Z$, $\beta\in\R$, and $K=\alpha n+\beta\in\Z$, where $n$ satisfies \eqref{eq:n1}--\eqref{eq:n2}. If \begin{equation} \alpha\rho+\beta x\pmod 1\ \in B\qquad(\rho\in\classes,\ 0\le x\le1),\label{eq:path} \end{equation} then, for some $i\in\{0,\ldots,q-1\}$, \begin{equation} Ka_i\equiv\pm\frac{n-1}{3}\modulo n.\label{eq:character} \end{equation} \end{lemma} \begin{proof} A continuous linear path contained in an arc of length $1/3$ has $|\beta|\le1/3$. Taking the two endpoints in \eqref{eq:path} shows that all $\alpha\rho$ have real representatives in a common interval $I\subseteq B$ of width at most $1/3-|\beta|$. Decompose the character in the independent CRT coordinates: \begin{equation} \alpha s\equiv \frac{u(s\bmod 3)}3+\frac{v(s\bmod 5)}5 +\sum_{j=1}^{q-1}\frac{c_j e_j(s)}{d_j}\modulo1,\label{eq:decompose} \end{equation} with integer coefficients $u,v,c_j$, taken modulo $3,5,d_j$, respectively. In the $h=0$ product in \eqref{eq:blocksize}, increasing $y_j$ by one changes the phase by $15c_j/d_j$ modulo one. Since all real representatives lie in $I$, their actual difference lies in $[-1/3,1/3]$. There is at most one representative of a given phase difference in that interval, so the actual difference is constant throughout the product. Denote it by $\delta_j$. The phase on the product is therefore affine in its coordinates, and its width is \begin{equation} \sum_j m_j|\delta_j|\le\frac13.\label{eq:width} \end{equation} Each $\delta_j=z_j/d_j$ for an integer $z_j$. Since $m_j=(d_j-1)/3$, a nonzero $z_j$ must equal $1$ or $-1$. Moreover at most one $z_j$ can be nonzero, since two would contribute at least $2/3-1/(3d_i)-1/(3d_j)>1/3$. Here all $d_j>8$. \emph{No active coordinate.} If all $z_j$ vanish, then $c_j=0$ modulo $d_j$, and the five block phases are $2u/3+vz/5$, with $z$ running through $\Z/5\Z$. For $v\ne0$ modulo $5$ these are five equally spaced points, which cannot lie in $I$. Thus $v=0$, and $u=1$ or $2$. The character $\alpha$ is consequently $1/3$ or $2/3$ modulo one. The integrality of $\alpha n+\beta$, together with $n\equiv1\modulo3$ and \eqref{eq:path}, forces $\beta=-1/3$ or $1/3$, respectively. These give \eqref{eq:character} with $a_0=1$. \emph{One active coordinate.} Suppose only the coordinate $j$ is active. Negating the character and $\beta$ preserves the hypothesis, so assume $\delta_j=1/d$, where $d=d_j$ and $a=5d$. We may take $c_j=(1-d)/15$, because $d\equiv1\modulo{15}$ and $15c_j\equiv1\modulo d$. Write $m=(d-1)/3$. The first phase of block $h$ is \begin{equation} P_h\equiv\frac{2u}3+\frac{(3v-1)(2+3h)}{15}+\frac{2+3h}{15d}\modulo1.\label{eq:firstphase} \end{equation} Each block is a progression with step $1/d$. Its width is $m/d$ when $h=0$ and $(m-1)/d$ otherwise. Since all blocks lie in $I$, their first phases have representatives in an interval of width at most \[ \frac13-\frac{m-1}{d}=\frac4{3d}. \] Successive first phases differ modulo one by $(3v-1)/5+1/(5d)$. Unless $v=2$ modulo $5$, its distance from an integer is at least $1/5-1/(5d)>4/(3d)$, because $d>8$. Hence $v=2$. The first phases then advance by $1/(5d)$. The $h=0$ block contains the real range of all five blocks because the other starts are shifted forward by at most $4/(5d)$ and their widths are smaller by $1/d$. Its initial phase is $2u/3+2/3+2/(15d)$ modulo one. Containment in $B$ forces $u=1$ modulo $3$: $u=0$ starts above $2/3$, and $u=2$ below $1/3$. The full range of phases is therefore \begin{equation} \left[\frac13+\frac2{3a},\,\frac23-\frac1a\right].\label{eq:phaserange} \end{equation} Its translates by $\beta x$ stay in $B$ only if \begin{equation} -\frac2{3a}\le\beta\le\frac1a.\label{eq:betarange} \end{equation} Using $\kappa_j\equiv6\modulo{15}$, formula \eqref{eq:decompose} now simplifies to \begin{equation} \alpha\equiv\frac13+\frac{\kappa_j}{3a}\modulo1.\label{eq:alpha} \end{equation} Indeed, $2/5+(1-d)\kappa_j/(15d)$ is congruent to $\kappa_j/(15d)$. The number \begin{equation} \left(\frac13+\frac{\kappa_j}{3a}\right)n+\frac1{3a} =\frac{(a+\kappa_j)n+1}{3a}\label{eq:integral} \end{equation} is integral, since its numerator is divisible by $a$ by \eqref{eq:n2} and by $3$ by \eqref{eq:congruences} and \eqref{eq:n1}. The interval \eqref{eq:betarange} has length $5/(3a)<1$ and contains $1/(3a)$. Thus integrality leaves precisely $\beta=1/(3a)$. Multiplying \eqref{eq:integral} by $3a$ shows that $3Ka\equiv1\modulo n$. As $n\equiv1\modulo3$, this gives $Ka\equiv(2n+1)/3\equiv-(n-1)/3\modulo n$. Negation covers the other sign. \end{proof} \section{From finite deficits to exact rigidity} We now prove Condition (iv) with the finite size bound \eqref{eq:nlarge}. No compactness or limiting argument is needed. \begin{proposition}\label{prop:finite} For the parameters above, $F(K)\le r$ implies \eqref{eq:character} for some $i$. In particular $D_K(a_i)=1>0$. \end{proposition} \begin{proof} Each individual deficit is at most $r$. By symmetry in $s$ and $-s$, every $s\in S$ satisfies \begin{equation} \frac{\res{Ks}n}{n}\in B_\varepsilon =\left[\frac13-\varepsilon,\frac23+\varepsilon\right],\qquad \varepsilon=\frac{r}{3n}.\label{eq:expanded} \end{equation} The width $w=1/3+2\varepsilon$ is less than $1/2$. Choose a residue class in $\classes$ not containing the possible involution $n/2$. Its positive representatives below $n$ form an uninterrupted progression of step $L$, with at least $n/L-1$ elements. The phases of consecutive representatives have differences in $[-w,w]$ and are all congruent to $KL/n$ modulo one. Since $2w<1$, these real differences are equal. Write their common value as $\delta=KL/n-p$, where $p\in\Z$. Telescoping gives $|\delta|(n/L-2)\le w$. Set $\alpha=p/L$ and $\beta=n\delta/L$. Then $K=\alpha n+\beta$, and \eqref{eq:nlarge} gives \begin{equation} |\beta|\le\frac{w}{1-2L/n}<\frac12.\label{eq:smallbeta} \end{equation} For an arbitrary $\rho\in\classes$, its first and last positive representatives below $n$ lie within $L$ of $0$ and $n$, respectively. Neither is the involution, since $n>2L$. Their phases in \eqref{eq:expanded} show that $\alpha\rho$ and $\alpha\rho+\beta$ have circular distance from $B$ at most \begin{equation} \varepsilon+|\beta|\frac Ln<\frac{r/3+L/2}{n}<\frac1L.\label{eq:griderror} \end{equation} Both phases belong to the grid $L^{-1}\Z/\Z$, because $\alpha=p/L$ and $\beta=K-pn/L$. The endpoints of $B$ belong to the same grid since $3\mid L$. A grid point outside $B$ is at distance at least $1/L$ from $B$, so both phases actually belong to $B$. Their representatives in $B$ differ by at most $1/3$. By \eqref{eq:smallbeta} that difference must equal $\beta$, since any nonzero integer shift of $\beta$ has magnitude greater than $1/2$. The interpolating segment stays in $B$, proving the hypothesis of Lemma~\ref{lem:rigidity}. This yields \eqref{eq:character}. If $m=(n-1)/3$, then $\min(m,n-m)=m$ and $n-3m=1$, so the resulting deficit is exactly one. \end{proof} \section{Disjoint three-step words}\label{sec:words} We finish the construction by proving Condition (iii). Fix $z\in J$, so $0100$ and $a_ja_j/3-14>0$ and $02(6r+3)$, so both choices can be made. The three summands are generic and avoid the involution, hence lie in $S$. Their sum is $W\equiv z\modulo n$, as required. \end{proof} Initially forbid $z$ and $-z$. After choosing a word, also forbid both signs of each of its three directions. Before the $r$th choice there are at most $2+6(r-1)$ forbidden residues, so Lemma~\ref{lem:avoid} applies at every stage. The resulting $r$ words avoid the target pair and have mutually disjoint sets of direction pairs. This proves Condition (iii). \begin{proof}[Proof of Theorem~\ref{thm:construction}] Lemma~\ref{lem:parameters} and the subsequent CRT choice supply the integer parameters for every $r\ge1$. Define $S$ by \eqref{eq:S} and add the chords \eqref{eq:chords}. Lemma~\ref{lem:ratios} and the discussion in Section~\ref{sec:core} prove Conditions (i) and (ii). Proposition~\ref{prop:finite} proves Condition (iv), and the preceding word construction proves Condition (iii). Theorem~\ref{thm:criterion} gives a finite $(4,r)$-graph. \end{proof} \section{Lean verification and computational checks}\label{sec:lean} The original formal development was supplied as a single file, \texttt{Solution.lean}, with the two imports requested by the challenge: \begin{quote} \texttt{import FormalConjectures.ErdosProblems.{\fontencoding{T1}\selectfont\guillemotleft{}944\guillemotright}}\\ \texttt{import TaskSupport} \end{quote} The code uses the namespace \texttt{Bounty.Erdos944Proof}. It is checked with Lean 4.33.1 and with warnings treated as errors. The 570 proved theorems in the original manuscript's count have no admitted proof placeholders. Their transitive proof dependencies use only the standard axioms \texttt{propext}, \texttt{Classical.choice}, and \texttt{Quot.sound}. None uses \texttt{sorryAx}. Reading the challenge theorem's type with the supplied elaborator does not use that theorem as a proof. \subsection{The complete target} The original file contains 9,548 lines, including every supporting proof and the following final theorem in the namespace \texttt{Bounty}: \begin{quote} \ttfamily theorem target : fcTypeOfName\% "Erdos944.erdos\_944" := by\\ \hspace*{1em}constructor\\ \hspace*{1em}\textperiodcentered{} intro \_ k hk r \_hr\\ \hspace*{2em}exact Erdos944Proof.erdos944\_all hk r\\ \hspace*{1em}\textperiodcentered{} intro \_\\ \hspace*{2em}trivial \end{quote} The audit driver separately checks that its type is \[ \mathrm{True}\longleftrightarrow \forall k\ge4\ \forall r\ge1\ \exists V\ \exists G,\quad G\text{ has the Erd\H{o}s 944 property for }k,r. \] It also applies the theorem directly to this explicit proposition. The three existence lemmas are \texttt{erdos944\_four}, \texttt{erdos944\_five}, and \texttt{erdos944\_ge\_six}. They have no additional mathematical hypotheses, and also cover $r=0$ and arbitrary target universes. The imported conjecture theorem is used only to obtain the requested type. Its admitted proof does not occur in the proof dependencies. The theorem \texttt{exists\_cyclic\_integer\_data} constructs the recursive CRT family, a sufficiently large order, and all unit directions. The full three-step word construction and its finite-set avoidance property are proved. The character argument is carried out with integers: finite rounding expresses $KL$ as an integer multiple of $n$ plus a bounded remainder, and the five CRT blocks force the frequency into the canonical cases. The Lean proof establishes constant coordinate steps, their exact divisibility, and coefficient sparsity, then determines the active frequency from adjacent block endpoints modulo fifteen. Integrality determines the remainder and gives a unit with deficit exactly one. Thus the arithmetic conditions of the graph construction criterion are all discharged. For $k\ge5$, the theorem \texttt{higher\_punctured} proves the vertex-deleted colorings for every positive $m$ and natural $q$. The row formula handles both parities of $k$. Equal-colored vertices have restricted index differences, which avoid all three distance families in both cyclic directions. These definitions and colorings follow Skottov\'a and Steiner~\cite[Section 4 and Appendix A]{SkottovaSteiner}. The proof also bounds the affected vertices by twice the number of monochromatic edges. Dividing a window into $2r+1$ disjoint blocks then produces an unaffected block of length $3n_{k,m}$. Local propagation from such a block is proved below and then converted into the required graph property. The theorem \texttt{higher\_clean\_block\_periodic} proves periodicity inside every unaffected block of three periods, for all $k\ge5$, including $k=6$ and $k=8$. Odd $k$ uses a partition into cliques. Even $k$ uses ten-vertex subgraphs of independence number two and an interval-counting argument. This formalizes the local-periodicity claim of Skottov\'a and Steiner~\cite[Claim 4.4]{SkottovaSteiner}. The periodic expected coloring retains the block's exact color counts and short-distance constraints. A color class larger than $2r$ in an interval of length $2m$ has a single parity: it contains an unaffected vertex, which excludes the opposite parity. Finally, for odd $k\ge5$, the unaffected prefix leaves only the expected colors at $i$ and $i-1$ as options at later indices $i<(q/2)n_{k,m}$. The even-color restriction and extension through the larger window are also proved. The theorem \texttt{higher\_expected\_local\_structure\_all} establishes the local color structure for every $k\ge6$: on each parity, changes of expected color occur at exactly one residue modulo $2m$. For odd $k\ge7$, each expected color class is one even-step block repeated periodically. For even $k\ge10$, it is two such blocks. The exceptional cases $k=6,8$ use finite ring configurations. These force two local color options and periodicity of the change positions. A duplicate color in a ring would remain fixed along an entire parity, contradicting an edge of length $2m$. Ring injectivity and an exact count of changes then give one change on each parity per period. These arguments formalize Skottov\'a and Steiner~\cite[Claims 4.6--4.7 and Appendix B]{SkottovaSteiner}, using finite certificates checked by Lean's kernel. \subsection{Completing propagation} Write $L=n_{k,m}$ for the period of the expected coloring and take $q=24r+12$, so the graph has order $qL+1$. We use $m=18r+3$ for $k\ge6$ and $m=18r+20$ for $k=5$. A coloring with at most $r$ bad edges has at most $2r$ affected vertices. A color occurring more than $2r$ times in any interval of length $2m$ therefore occurs at only one parity in that interval. For even $k$, put $n=k-1$ and $s=\lfloor n/2\rfloor$. Two adjacent rings have positions $2ma+b$, where $0\le am$. But every actual color in a $2m$-interval occurs at most $m$ times: a count at most $2r$ is already bounded by $m$, and a larger count has a single parity. This contradiction excludes the first deviation for $k=5$. Thus a clean prefix determines the actual coloring throughout the required larger window. Every interval of length $(6r+3)L$ contains a clean $3L$-block. Reflecting that block and applying prefix agreement proves $c(v+L)=c(v)$ for every vertex $v$. Since $\gcd(L,qL+1)=1$, such a coloring is constant, contradicting a proper edge in the clean block. Every $(k-1)$-coloring therefore has more than $r$ bad edges. Combining this with the punctured colorings proves the higher-color existence theorems and completes \texttt{Bounty.target}. The main correspondences are listed below. Names are relative to \texttt{Bounty.Erdos944Proof}, except the final target. {\small \begin{longtable}{@{}>{\raggedright\arraybackslash}p{.39\linewidth}>{\raggedright\arraybackslash}p{.59\linewidth}@{}} \hline Mathematical component & Lean theorem\\\hline \endhead Punctured colorings of the augmented graph & \texttt{augmentedGraph\_punctured}\\ Filled Hamiltonian gaps & \texttt{augmentedGraph\_filled\_gaps}\\ Height character for any unit & \texttt{exists\_group\_flux\_character}\\ Deficit estimate with retained lifts & \texttt{exists\_character\_with\_lifts}\\ Winding induction & \texttt{andrasfai\_cycle\_flux\_le}\\ Two-sided gap bound & \texttt{path\_gain\_bounds\_of\_badEdges\_bound}\\ Flux bound from all gaps & \texttt{flux\_bounds\_of\_andrasfai\_gaps}\\ The graph construction criterion & \texttt{erdos944\_four\_of\_cyclic\_data}\\ Short compatibility of constructed units & \texttt{cyclic\_data\_shortCompatible}\\ Disjoint words from avoidance & \texttt{hasSignedWords\_of\_avoidance}\\ Transport to arbitrary universes & \texttt{erdos944\_universe\_lift}\\ Arbitrarily large finite CRT solutions & \texttt{exists\_large\_crt}\\ Choice of $q=3t+1$ coprime to $15$ & \texttt{exists\_gap\_parameter}\\ Canonical deficit equal to one & \texttt{canonical\_deficit\_one}\\ Recursive integer data for every $r$ & \texttt{exists\_cyclic\_integer\_data}\\ Exact normalized-coordinate formula & \texttt{normalized\_coordinate\_mul}\\ Unique five-block CRT grid & \texttt{existsUnique\_generic\_grid\_class}\\ Generic residues give signed connections & \texttt{cyclic\_data\_generic\_signed\_mem}\\ Avoiding a finite set in a progression & \texttt{exists\_progression\_point\_avoiding}\\ Splitting a coordinate sum into three & \texttt{split\_three\_residue\_coordinates}\\ Uniform three-step word avoidance & \texttt{cyclic\_data\_word\_avoidance}\\ Finite rounding to an exact character & \texttt{cyclic\_data\_rounded\_character}\\ Affine phases on a CRT block & \texttt{middleThirdCharacter\_grid\_affine}\\ Sparsity of the CRT coefficients & \texttt{middleThirdCharacter\_sparse\_coefficients}\\ Exact periodic character rigidity & \texttt{cyclic\_data\_periodic\_rigidity}\\ Four-color existence for every $r$ & \texttt{erdos944\_four}\\ Higher-color punctured colorings & \texttt{higher\_punctured}\\ An unaffected consecutive block & \texttt{higher\_exists\_unaffected\_block}\\ Local periodicity for every $k\ge5$ & \texttt{higher\_clean\_block\_periodic}\\ Periodic expected-color counts & \texttt{higherExpectedColor\_window\_count}\\ Parity of large short color classes & \texttt{higher\_short\_color\_class\_single\_parity}\\ Two color options for odd $k$ & \texttt{higher\_odd\_clean\_prefix\_two\_options}\\ Local color structure for every $k\ge6$ & \texttt{higher\_expected\_local\_structure\_all}\\ Injective rings for $k=6,8$ & \texttt{higher\_small\_ring\_color\_injective}\\ Reduction to local propagation & \texttt{higher\_erdos944\_of\_local\_propagation}\\ Two color options for even $k$ & \texttt{higher\_even\_clean\_prefix\_two\_options}\\ First-deviation count for $k=5$ & \texttt{five\_first\_deviation\_impossible}\\ Existence for $k=5$ & \texttt{erdos944\_five}\\ Existence for every $k\ge6$ & \texttt{erdos944\_ge\_six}\\ All-color existence & \texttt{erdos944\_all}\\ Exact challenge proposition & \texttt{Bounty.target}\\\hline \end{longtable} } \subsection{Pinned environment} The original checked environment used the following revisions. Its \texttt{validation.json} recorded the exact source hash and audit results. \begin{itemize} \item Lean compiler: \texttt{819816b2e0a3bf405af45ae5c7af2491d8f5bee6}. \item Formal Conjectures audited revision: \texttt{8432eac998110a563e03df65a28c117e97c8c142}. \item mathlib revision~\cite{Mathlib}: \texttt{0df444a360eaa60ab8c11dca51a86af692955474}. \end{itemize} The challenge source uses \texttt{google.answer=always\_true} to select the displayed proposition. The original audit covered all 570 theorem dependency closures. The manuscript and original archive used the same checked snapshot. The later \href{https://github.com/lkruer/conjectures/tree/d42416ace335b42e05c6f46d250c869bce4b5239/problems/erdos-944/lean/reproducible}{pinned reproducible prize package} links the historical and accepted sources and checks the explicit finite target. Its \href{https://github.com/lkruer/conjectures/blob/cae4f9f05dab5b0f78afb1f5b16e5ef828e2d397/problems/erdos-944/lean/reproducible/verification/REPORT.md}{recorded clean target build and axiom audit} covers 2,339 declarations using cached dependencies. The \href{https://conjectures.io/results/e7afff2c-bb07-4fa8-92b6-67a530aaad70}{separate Conjectures verification record} applies to the accepted challenge source. The \href{https://github.com/lkruer/conjectures/blob/d42416ace335b42e05c6f46d250c869bce4b5239/problems/erdos-944/SOURCE_HISTORY.md}{source history} distinguishes these versions from one another and from the original manuscript snapshot. \subsection{Finite checks} The exact-arithmetic program checks the integer parameters, residue and ratio identities, and selected word certificates. Recorded instances follow. The graphs are not materialized at these enormous orders. \begin{center} \begin{tabular}{@{}rrrrr@{}} \hline $r$ & $q$ & Digits of $n$ & Digits of $L$ & Words checked\\\hline 1 & 4 & 78 & 38 & 16\\ 2 & 7 & 714 & 355 & 38\\ 3 & 13 & 50,220 & 25,108 & 75\\\hline \end{tabular} \end{center} Character enumerations were also recorded for moduli $465$ and $28{,}365$. These finite checks supplement the symbolic Lean proofs of general rigidity and graph existence. The complete target is proved symbolically in Lean. \section*{Acknowledgment of AI assistance} OpenAI Codex assisted with mathematical exploration, computational checks, Lean proof development, and manuscript drafting. Liam Kruer and Jensen Kohlmeyer are the listed authors. Section~\ref{sec:lean} records what Lean has verified, the source correspondence, and the pinned environment. \begin{thebibliography}{4} \bibitem{SkottovaSteiner} E. Skottov\'a and R. Steiner, \emph{Critical edge sets in vertex-critical graphs}, preprint, arXiv:2508.08703 (2025), \url{https://arxiv.org/abs/2508.08703}. \bibitem{Bloom} The Formal Conjectures Authors, \emph{Formal Conjectures}, \texttt{FormalConjectures/ErdosProblems/944.lean}, \url{https://github.com/google-deepmind/formal-conjectures}. \bibitem{Formal} Conjectures.io, \emph{Erd\H{o}s 944 formalized challenge}, \url{https://conjectures.io/problems/erdos944-erdos-944/challenge?mode=formalized}, accessed September 10, 2026. \bibitem{Mathlib} The mathlib Community, \emph{mathlib4}, \url{https://github.com/leanprover-community/mathlib4}. \end{thebibliography} \end{document}