betaFeedback

WorksMathematics

Vertex-critical four-chromatic graphs with no small critical edge set

Abstract

For every positive integer rr, we construct a finite four-chromatic graph such that deleting any vertex lowers the chromatic number, and deleting any set of at most rr edges preserves it. The proof combines punctured cyclic three-colorings, an integral height character, an Andrásfai winding bound, and a Chinese remainder construction with an exact classification of its small-deficit characters. Together with the higher-color result of Skottová and Steiner, this gives finite existence for every chromatic number at least four. The accompanying Lean formalization checks the finite-existence theorem.

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)(k,r)-graph for a finite graph GG satisfying

χ(G)=k,χ(G−v)=k−1(v∈V(G)),χ(G−E′)=k(E′⊆E(G), ∣E′∣≤r).(1)\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). \tag*{(1)}

The existence statement of Erdős problem 944 asks whether a (k,r)(k,r)-graph exists for every k≥4k \ge4 and r≥1r \ge1. It is also the statement selected by the Formal Conjectures challenge [2, 3]. Skottová and Steiner [1 Theorem 1.3] prove the existence of such graphs for every k≥5k \ge5 and r≥1r \ge1. Their result leaves the four-color case.

Theorem 1.1 (Construction). For every integer r≥1r \ge1, there is a finite (4,r)(4,r)-graph.

Corollary 1.2. For every k≥4k \ge4 and r≥1r \ge1, there is a finite (k,r)(k,r)-graph.

The corollary combines Theorem 1.1 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.

Status of the proof and its formalization

This is a research manuscript for mathematical review. Sections 2–7 give the four-color proof in ordinary mathematics. The accompanying Lean file proves that theorem for every natural rr, 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á and Steiner and proves its required existence statement. This includes the exceptional cases k=5,6,8k = 5, 6, 8, with a paired-ring argument for even kk and an overlapping-interval count for k=5k = 5. All witnesses are transported to the universe required by the challenge. The theorem Bounty.target proves exactly the displayed proposition for every k≥4k \ge4 and r≥1r \ge1. Section 8 gives the proof correspondence and pinned verification environment. The symbolic proof is independent of the supplementary finite computations.

Notation

For an integer xx and a positive integer nn, write [x]n[x]_n for the least nonnegative residue of xx modulo nn. We identify elements of Z/nZ\mathbb{Z}/n\mathbb{Z} with their least representatives when inequalities or residues modulo 3 are used. A direction pair is an unordered pair {s,−s}\{s,-s\} in Z/nZ\mathbb{Z}/n\mathbb{Z}. If SS is an inverse-closed set of nonzero directions, Cay⁡(Z/nZ,S)\operatorname{Cay}(\mathbb{Z}/n\mathbb{Z},S) has the edges {v,v+s}\{v,v+s\} for s∈Ss \in S. An edge is bad for a coloring when its endpoints receive the same color. All edge counts below count distinct undirected edges.

A cyclic graph construction criterion

Suppose that n≡1(mod3)n \equiv1 \pmod{3} and put

Nn={1,n−1}∪{s:0<s<n, s≡2(mod3)}.(2)N_n=\{1,n-1\}\cup\{s:0<s<n,\ s\equiv2\pmod{3}\}. \tag*{(2)}

Fix r≥1r\geq1, t≥rt\geq r, and q=3t+1q=3t+1, with q∣nq\mid n and q<nq<n. Let a0,…,aq−1a_0,\ldots,a_{q-1} be units modulo nn with distinct direction pairs. Let SS be inverse-closed, contain all ±ai\pm a_i, and contain neither zero nor an element of order two. Let J={s∈S:0<s<n/2}J=\{s\in S:0<s<n/2\}. Thus JJ contains exactly one representative of every direction pair in SS. For K∈ZK\in\mathbb{Z}, define

DK(s)=max⁡{0,n−3min⁡([Ks]n,n−[Ks]n)},F(K)=∑s∈JDK(s).(3)D_K(s)=\max\{0,n-3\min([Ks]_n,n-[Ks]_n)\},\qquad F(K)=\sum_{s\in J}D_K(s). \tag*{(3)}

The deficit is unchanged when ss or KK is negated.

Theorem 2.1 (Construction criterion). Suppose the following conditions hold.

(i) S⊆aiNnS\subseteq a_iN_n for every ii.

(ii) For i≠ji\ne j and ℓ∈{4,7,…,q}\ell\in\{4,7,\ldots,q\}, [ℓaiaj−1]n≡2(mod3)[\ell a_i a_j^{-1}]_n\equiv2\pmod{3}.

(iii) Every s∈Js\in J is the sum of each of rr three-step words in SS. Their direction pairs avoid {s,−s}\{s,-s\} and the sets of direction pairs used by different words are disjoint.

(iv) If F(K)≤rF(K)\leq r, then DK(ai)>0D_K(a_i)>0 for some ii.

Start with H=Cay⁡(Z/nZ,S)H=\operatorname{Cay}(\mathbb{Z}/n\mathbb{Z},S). For each ii, and every vertex xx with x≡i(modq)x\equiv i\pmod q, add the edges

{x+jai,x+(j+ℓ)ai},ℓ∈{4,7,…,q},0≤j≤q−ℓ.(4)\{x+ja_i,x+(j+\ell)a_i\},\qquad\ell\in\{4,7,\ldots,q\},\quad0\leq j\leq q-\ell. \tag*{(4)}

Identify repeated edges. The resulting simple graph GG is a (4,r)(4,r)-graph.

Punctured colorings

Delete a vertex vv, let i=[v]qi=[v]_q, and color every remaining vertex by

cv(u)=[[ai−1(u−v)]n]3(u≠v).(5)c_v(u)=[[a_i^{-1}(u-v)]_n]_3\qquad(u\ne v). \tag*{(5)}

If a normalized difference is 2 modulo 3, its color difference is 2 without a wrap and 1 with a wrap, since n≡1(mod3)n\equiv1\pmod{3}. Differences 1 and −1-1 are also proper after coordinate zero is deleted. Condition (i) therefore makes every core edge proper.

For a chord of type ii, the normalized forward length is 1 modulo 3. The chord lies inside a qq-step gap between consecutive vertices whose residue modulo qq is ii. Such a gap has no vertex of that residue class in its interior because aia_i remains a unit modulo qq. The puncture vv 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−vG-v is three-colorable for every vv, and assigning one new color to vv shows that χ(G)≤4\chi(G)\leq4.

Height characters

For different colors b,c∈Z/3Zb,c\in\mathbb{Z}/3\mathbb{Z}, let σ(b,c)\sigma(b,c) be the unique element of {−1,1}\{-1,1\} congruent to c−bc-b modulo 3.

Lemma 2.2 (Height character). Let UU be an inverse-closed set of directions generating Z/nZ\mathbb{Z}/n\mathbb{Z}, and suppose its Cayley graph is properly three-colored. There is a character K∈Z/nZK\in\mathbb{Z}/n\mathbb{Z} and a translation-invariant mean height increment θu\theta_u for every oriented generator, satisfying

∣θu∣≤1,θu≡3+6Kun(mod6).(6)|\theta_u|\leq1,\qquad\theta_u\equiv3+\frac{6Ku}{n}\pmod{6}. \tag*{(6)}

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 ss has mean congruent to 3+6Ks/n3+6Ks/n modulo 66.

Proof. Choose representatives u1,…,udu_1,\ldots,u_d for the generator pairs and pull the coloring back under the map Zd→Z/nZ\mathbb{Z}^d \to\mathbb{Z}/n\mathbb{Z} taking eje_j to uju_j. Give each oriented grid edge the increment σ\sigma of its endpoint colors. The sum around a square is even, divisible by 33, and between −4-4 and 44. 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 hh on Zd\mathbb{Z}^d.

Write Λ\Lambda for the kernel of the map. For λ∈Λ\lambda\in\Lambda, the difference h(x+λ)−h(x)h(x+\lambda)-h(x) is divisible by 33. Its change when xx moves by a unit grid step is in {−2,0,2}\{-2,0,2\} and divisible by 33, so that difference is independent of xx. Denote it by ϕ(λ)\phi(\lambda). It is additive in λ\lambda and extends to a real linear functional θ⋅x\theta\cdot x, since Λ\Lambda has finite index. The period nejne_j gives ∣θj∣≤1|\theta_j|\leq1. Height parity and color congruence give

ϕ(λ)≡∑jλj(mod2),ϕ(λ)≡0(mod3).\phi(\lambda)\equiv\sum_j\lambda_j\pmod2,\qquad\phi(\lambda)\equiv0\pmod3.

Hence (θ−31)/6(\theta-3\mathbf{1})/6 takes integral values on Λ\Lambda. Modulo integral functionals it factors through a character of the cyclic quotient, proving (6).

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 θj\theta_j. Translation permutes the starting vertices, and therefore averaging a word adds the signed generator means. The contribution of the constant 33 is 33 modulo 66 for an odd word. □

Bad edges and the deficit bound

Suppose a three-coloring of GG has at most rr bad edges. A direction pair in SS is called bad if at least one of its translated edges is bad. There are at most rr such pairs, since different direction pairs have disjoint edge sets. As q>rq>r, one of the chosen unit directions has no bad edge. The remaining proper directions still generate Z/nZ\mathbb{Z}/n\mathbb{Z}.

If a target direction ss is bad, its rr words in Condition (iii) avoid its own pair. At most r−1r-1 other bad pairs can spoil these mutually disjoint words, so at least one is wholly proper. If ss is proper, use the word (s,s,−s)(s,s,-s) instead. Apply Lemma 2.2 to the proper directions and let δs(v)\delta_s(v) be the height increment of a selected three-step word for ss, starting at vv. It belongs to {−3,−1,1,3}\{-3,-1,1,3\} and has the endpoint color difference as its residue modulo 33. Consequently it is ±1\pm1 at a proper ss-edge and ±3\pm3 at a bad one. If βs\beta_s is the number of bad ss-edges and θs\theta_s is the mean of these word increments, then

θs≡3+6Ksn(mod6),∣θs∣≤1+2βsn.(7)\theta_s\equiv3+\frac{6K_s}{n}\pmod6,\qquad|\theta_s|\leq1+\frac{2\beta_s}{n}. \tag*{(7)}

There are exactly nn edges in this direction pair: the assumption that ss is not an involution makes v↦{v,v+s}v\mapsto\{v,v+s\} injective. If x=⌊Ks⌋/nx=\lfloor K_s\rfloor/n, the least possible absolute value of a real number congruent to 3+6x3+6x modulo 66 is 3−6min⁡(x,1−x)3-6\min(x,1-x). (7) gives βs≥DK(s)\beta_s\geq D_K(s). Summing over the representatives in JJ therefore proves

F(K)≤∑s∈Jβs≤r.(8)F(K)\leq\sum_{s\in J}\beta_s\leq r. \tag*{(8)}

Moreover, DK(s)>0D_K(s)>0 forces ∣θs∣>1|\theta_s|>1.

The winding inequality

Let BtB_t have vertex set {0,…,3t+1}\{0,\ldots,3t+1\} and an edge ijij, with i<ji<j, exactly when j−i≡1(mod3)j-i\equiv1\pmod3. In particular it contains the consecutive cycle edges, including the closing edge.

Lemma 2.3 (Winding bound). Suppose a three-coloring of BtB_t has at most tt bad edges. Along the path 0,1,…,3t+10,1,\ldots,3t+1, assign increments ±1\pm1 to proper edges and ±3\pm3 to bad edges, each congruent modulo 33 to its color difference. The sum of the increments lies between −(3t+1)-(3t+1) and 3t+13t+1.

Proof. For a color pair define its maximal increment mm to be 33 if the colors are equal, 11 if the color increases by 11 modulo 33, and −1-1 otherwise. For a cyclic color word of length 3t+23t+2, let CC be the sum of these maximal increments. We prove by induction that at most tt bad BtB_t edges imply C≤3tC \le3t.

For t=0t=0, the graph is a proper edge traversed in both directions, so C=0C=0. If t>0t>0 and there are no bad cycle edges, then C≤3t+2C \le3t+2. Its parity agrees with 3t+23t+2 and it is divisible by 33, giving C≤3tC \le3t.

Otherwise let bb be the number of bad cycle edges, so 1≤b≤t1 \le b \le t. The 3t+2−b>2b3t+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 BtB_t, since 3t+2≡2(mod3)3t+2 \equiv2 \pmod{3} and reversing an allowed cyclic difference again gives a difference 11 modulo 33.

The remaining induced graph, in its cyclic order, is Bt−1B_{t-1}. At least the initial bad edge disappears. If s∈{−3,−1,1,3}s \in\{-3,-1,1,3\} is the sum of the following three proper increments, the four removed increments sum to 3+s3+s. The maximal increment on the new bridge is, respectively, 3,−1,1,33,-1,1,3. Thus the old cycle sum is at most the new one plus 33. Induction proves C≤3tC \le3t.

The maximal path increments dominate the assigned increments. The closing increment is at least −1-1, so a path sum exceeding 3t+13t+1 would give C>3tC>3t. This proves the upper bound. Reverse the path and negate its increments to obtain the lower bound. □

Proof of Theorem 2.1. The punctured colorings prove the vertex-deletion assertions and χ(G)≤4\chi(G) \le4. If a three-coloring had at most rr bad edges, (8) and Condition (iv) would supply an aia_i with ∣θai∣>1\lvert\theta_{a_i}\rvert>1. Reverse the orientation if necessary. The sum of its word increments around its unit Hamiltonian cycle then exceeds nn. Partition the cycle into its n/qn/q designated gaps of length q=3t+1q=3t+1. Some gap has sum exceeding qq. Its vertices span BtB_t by (4) and the unit core edges, contradicting Lemma 2.3, since the entire graph has at most r≤tr \le t bad edges. Reversal preserves the same gap graphs.

Thus every three-coloring of GG has more than rr bad edges. In particular GG is not three-colorable, so χ(G)=4\chi(G)=4. A three-coloring after deleting at most rr edges would have at most rr bad edges in GG, which is impossible. Finally, χ(G−v)\chi(G-v) cannot be at most 22, since adding vv in a new color would three-color GG. Therefore (1) holds with k=4k=4. □

The integer parameter construction

Fix r≥1r \ge1. Choose t=rt=r unless 5∣3r+15 \mid3r+1, in which case choose t=r+1t=r+1. Then q=3t+1q=3t+1 is coprime to 1515. Put

D=30q,M=150q=5D,a0=1.(9)D=30q,\qquad M=150q=5D,\qquad a_0=1. \tag*{(9)}

For 1≤j<q1 \le j<q, recursively choose integers κj,dj,aj\kappa_j,d_j,a_j satisfying

κj≡0(mod3),κj≡1(modM−5),(10)\kappa_j \equiv0 \pmod{3},\qquad\kappa_j \equiv1 \pmod{M-5}, \tag*{(10)}
dj=D(κj−1)+1,aj=5dj,(11)d_j=D(\kappa_j-1)+1,\qquad a_j=5d_j, \tag*{(11)}
κj≥6,aj>10qaj−1,(12)\kappa_j \ge6,\qquad a_j>10qa_{j-1}, \tag*{(12)}
dj≡κi−1(moddi)(1≤i<j).(13)d_j\equiv\kappa_i^{-1}\pmod{d_i}\qquad(1\le i<j). \tag*{(13)}

Lemma 3.1. These choices exist. The djd_j are pairwise coprime, and for every $j\ge 1,

dj≡1(mod15),κj≡6(mod15),gcd⁡(κj,aj)=1,aj≡2(mod3),aj≡5(modq).(14)d_j\equiv1\pmod{15},\qquad\kappa_j\equiv6\pmod{15},\qquad\gcd(\kappa_j,a_j)=1,\qquad a_j\equiv2\pmod{3},\qquad a_j\equiv5\pmod{q}. \tag*{(14)}

Proof. Every did_i is 1 modulo DD. Since κi≡1(mod5(D−1))\kappa_i \equiv1 \pmod{5(D-1)}, it is also 1 modulo D−1D-1, and di≡1d_i \equiv1 modulo M−5M-5 by (11). Thus did_i is coprime to both DD and M−5=5(D−1)M-5=5(D-1). A common divisor of κi\kappa_i and did_i divides D−1D-1. As κi≡1(modD−1)\kappa_i \equiv1 \pmod{D-1}, this proves gcd⁡(κi,di)=1\gcd(\kappa_i,d_i)=1.

For a new index jj, condition (13) is equivalent to

κj≡D−1(κi−1+D−1)(moddi)(i<j).(15)\kappa_j \equiv D^{-1}(\kappa_i^{-1}+D-1) \pmod{d_i} \qquad(i<j). \tag*{(15)}

The moduli 3, M−5M-5, and the earlier did_i are pairwise coprime. Indeed, M−5≡1(mod3)M-5 \equiv1 \pmod3, the did_i are coprime to 3(M−5)3(M-5) by the observations above, and their pairwise coprimality follows inductively from (13). The Chinese remainder theorem supplies an arithmetic progression of choices for κj\kappa_j. Take a sufficiently large member to satisfy (12).

Finally DD is divisible by 15, and κj\kappa_j is 0 modulo 3 and 1 modulo 5, proving the first two congruences in (14). The coprimality with aja_j follows from the coprimality with djd_j and κj≡1(mod5))\kappa_j \equiv1 \pmod5). The two congruences for aja_j follow from aj=5dja_j=5d_j and D=30qD=30q.

Set

P=5∏j=1q−1dj,L=3P.(16)P=5\prod_{j=1}^{q-1}d_j,\qquad L=3P. \tag*{(16)}

Choose a positive integer nn with

n≡1(mod3),n≡0(modq),(17)n \equiv1 \pmod3,\qquad n \equiv0 \pmod q, \tag*{(17)}
n≡−κj−1(modaj)(1≤j<q),(18)n \equiv-\kappa_j^{-1} \pmod{a_j}\qquad(1\leq j<q), \tag*{(18)}
n>1000(r+1)qL2.(19)n>1000(r+1)qL^2. \tag*{(19)}

Such integers form a nonempty progression of step qLqL. To see this, separate the common factor 5 of the aja_j. Their prescribed residues are all −1-1 modulo 5, because κj≡1(mod5)\kappa_j \equiv1 \pmod5. The remaining moduli djd_j are pairwise coprime and coprime to 3q3q, while qq is coprime to 15. The Chinese remainder theorem therefore applies to 33, qq, 5, d1,…,dq−1d_1,\ldots,d_{q-1}, and an arbitrarily large member may be chosen. For a deterministic choice, take the least member satisfying (19).

Each aja_j is a unit modulo nn, and its least positive inverse for j≥1j\geq1 is

[aj−1]n=1+κjnaj.(20)[a_j^{-1}]_n=\frac{1+\kappa_j n}{a_j}. \tag*{(20)}

The numerator is divisible by aja_j by (18). Since 0<κj<aj0<\kappa_j<a_j and nn is larger than all the parameters aja_j, the displayed quotient is strictly between 0 and nn.

Lemma 3.2 (Short compatible ratios). For all distinct indices i,ji,j,

0<[aiaj−1]n<nq,[aiaj−1]n≡2(mod3).(21)0<[a_i a_j^{-1}]_n<\frac{n}{q},\qquad[a_i a_j^{-1}]_n\equiv2\pmod3. \tag*{(21)}

Consequently the aia_i have distinct direction pairs.

Proof. When j=0j=0, the representative is aia_i. Equation (14) and the size of nn give the result. Suppose j>0j>0 and set ℓ=[aiκj]aj\ell=[a_i\kappa_j]_{a_j}. Equation (20) gives the integer representative

Rij=ai+ℓnaj.(22)R_{ij}=\frac{a_i+\ell n}{a_j}. \tag*{(22)}

We check that it is less than n/qn/q, which also confirms that it is the least positive representative. If i=0i=0, then ℓ=κj\ell=\kappa_j, and ℓ/aj<1/(4q)\ell/a_j<1/(4q). If i>j≥1i>j\geq1, condition (13) gives ℓ=5\ell=5, again with ℓ/aj<1/(4q)\ell/a_j<1/(4q). If 0<i<j0<i<j, use

aiκjaj=(κi−1)+5M+aiaj(1−5M).(23)\frac{a_i\kappa_j}{a_j}=(\kappa_i-1)+\frac{5}{M}+\frac{a_i}{a_j}\left(1-\frac{5}{M}\right). \tag*{(23)}

The fractional part is positive and less than 1/(30q)+1/(10q)<1/(4q)1/(30q) + 1/(10q) < 1/(4q). The integer part is κi−1\kappa_i - 1. Thus ℓ≡2(mod3)\ell\equiv2 \pmod{3} in both cases i,j>0i,j > 0, i≠ji \ne j. For i=0i = 0 we instead have ℓ≡0(mod3)\ell\equiv0 \pmod{3}. Using aj≡2(mod3)a_j \equiv2 \pmod{3} and n≡1(mod3)n \equiv1 \pmod{3} in (22) now gives Rij≡2(mod3)R_{ij} \equiv2 \pmod{3} in every case.

Since ai≤P=L/3a_i \le P = L/3, the bound on nn implies n>4qmax⁡iain > 4q \max_i a_i. Equation (22) consequently gives 0<Rij/n<1/(2q)0 < R_{ij}/n < 1/(2q) when j>0j > 0. This proves (21). Equality ai=aja_i = a_j modulo nn would make their ratio 11, while ai=−aja_i = -a_j would make it n−1n - 1. Neither has residue 22 modulo 33.

The core and its periodic residue classes

Define

S=(⋂i=0q−1aiNn)∖{n/2},(24)S = \left(\bigcap_{i=0}^{q-1} a_i N_n\right) \setminus\{n/2\}, \tag*{(24)}

where the last removal is made only when nn is even. The set NnN_n is inverse-closed because the negative of a residue 22 modulo 33 has the same residue, since n≡1(mod3)n \equiv1 \pmod{3}. Thus SS is inverse-closed and has no involution. Lemma 3.2 puts all ±ai\pm a_i in SS. It proves Conditions (i) and (ii) as well. For ℓ≤q\ell\le q with ℓ≡1(mod3)\ell\equiv1 \pmod{3}, the product of ℓ\ell with an off-diagonal ratio is less than nn and is 22 modulo 33.

For 1≤j<q1 \le j < q and an integer ss, write ej(s)=[κjs]aje_j(s) = [\kappa_j s]_{a_j}. For 0<s<n0 < s < n, equation (20) yields the exact identity

[aj−1s]n=s+ej(s)naj.(25)[a_j^{-1}s]_n = \frac{s + e_j(s)n}{a_j}. \tag*{(25)}

The right side is a positive integer less than nn, because 0≤ej(s)<aj0 \le e_j(s) < a_j and 0<s<n0 < s < n.

Apart from the residues ±ai\pm a_i, membership in the intersection in (24) is equivalent to

s≡2(mod3),ej(s)≡2(mod3)(1≤j<q).(26)s \equiv2 \pmod{3}, \qquad e_j(s) \equiv2 \pmod{3} \qquad(1 \le j < q). \tag*{(26)}

Indeed, a normalized coordinate equals 11 or n−1n-1 only at the two corresponding orientations. Away from those exceptions, every normalized coordinate must be 22 modulo 33. Equation (25), with aj≡2(mod3)a_j \equiv2 \pmod{3}, gives (26). Conversely those congruences make every coordinate 22 modulo 33.

Call (26) the generic condition. It has period LL, independently of nn. Let R⊆Z/LZ\mathcal{R} \subseteq\mathbb{Z}/L\mathbb{Z} be its residue classes. Every positive representative below nn of a class in R\mathcal{R} belongs to SS, except the possible involution. The Chinese remainder theorem describes R\mathcal{R} as five products. Put mj=(dj−1)/3m_j = (d_j - 1)/3. For h∈{0,1,2,3,4}h \in\{0,1,2,3,4\}, impose

s≡2(mod3),s≡2+3h(mod5),ej(s)=2+3h+15yj.(27)s \equiv2 \pmod{3}, \qquad s \equiv2 + 3h \pmod{5}, \qquad e_j(s) = 2 + 3h + 15y_j. \tag*{(27)}

where the coordinates are independent and range over

0≤yj≤mj(h=0),0≤yj≤mj−1(h>0).(28)0 \le y_j \le m_j \quad(h = 0), \qquad0 \le y_j \le m_j - 1 \quad(h > 0). \tag*{(28)}

To check this, use κj≡1(mod5)\kappa_j \equiv1 \pmod{5}, so that ej(s)e_j(s) and ss have the same residue modulo 55. The residue 22 modulo 33 fixes the least representative modulo 1515 as 2+3h2 + 3h. Since dj≡1(mod15)d_j \equiv1 \pmod{15}, listing these representatives in [0,5dj)[0,5d_j) gives exactly (28). The eje_j coordinates modulo djd_j, together with the residues modulo 33 and 55, are independent CRT coordinates. Every block is nonempty, so in particular R\mathcal{R} contains more than one class.

Exact character rigidity

Let B=[1/3,2/3]⊆R/ZB = [1/3,2/3] \subseteq\mathbb{R}/\mathbb{Z}. The following lemma is the arithmetic classification on which the construction rests.

Lemma 5.1 (Rigidity of the periodic part). Suppose α∈L−1Z\alpha\in L^{-1}\mathbb{Z}, β∈R\beta\in\mathbb{R}, and K=αn+β∈ZK = \alpha n + \beta\in\mathbb{Z}, where nn satisfies (17)–(18). If

αρ+βx(mod1)∈B(ρ∈R, 0≤x≤1),(29)\alpha\rho+ \beta x \pmod{1} \in B \qquad(\rho\in\mathcal{R},\ 0 \le x \le1), \tag*{(29)}

then, for some i∈{0,…,q−1}i \in\{0,\ldots,q-1\},

Kai≡±n−13(modn).(30)Ka_i \equiv\pm\frac{n-1}{3} \pmod n. \tag*{(30)}

Proof. A continuous linear path contained in an arc of length 1/31/3 has ∣β∣≤1/3|\beta| \le1/3. Taking the two endpoints in (29) shows that all αρ\alpha\rho have real representatives in a common interval I⊆BI \subseteq B of width at most 1/3−∣β∣1/3-|\beta|.

Decompose the character in the independent CRT coordinates:

αs≡u(s mod 3)3+v(s mod 5)5+∑j=1q−1cjej(s)dj(mod1),(31)\alpha s \equiv\frac{u(s \bmod3)}{3}+\frac{v(s \bmod5)}{5}+\sum_{j=1}^{q-1}\frac{c_j e_j(s)}{d_j}\pmod1, \tag*{(31)}

with integer coefficients u,v,cju,v,c_j, taken modulo 3,5,dj3,5,d_j, respectively. In the h=0h=0 product in (28), increasing yjy_j by one changes the phase by 15cj/dj15c_j/d_j modulo one. Since all real representatives lie in II, their actual difference lies in [−1/3,1/3][-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 δj\delta_j. The phase on the product is therefore affine in its coordinates, and its width is

∑jmj∣δj∣≤13.(32)\sum_j m_j|\delta_j| \le\frac{1}{3}. \tag*{(32)}

Each δj=zj/dj\delta_j=z_j/d_j for an integer zjz_j. Since mj=(dj−1)/3m_j=(d_j-1)/3, a nonzero zjz_j must equal 11 or −1-1. Moreover at most one zjz_j can be nonzero, since two would contribute at least 2/3−1/(3di)−1/(3dj)>1/32/3-1/(3d_i)-1/(3d_j)>1/3. Here all dj>8d_j>8.

No active coordinate. If all zjz_j vanish, then cj=0c_j=0 modulo djd_j, and the five block phases are 2u/3+vz/52u/3+vz/5, with zz running through Z/5Z\mathbb{Z}/5\mathbb{Z}. For v≠0v\ne0 modulo 55 these are five equally spaced points, which cannot lie in II. Thus v=0v=0, and u=1u=1 or 22. The character α\alpha is consequently 1/31/3 or 2/32/3 modulo one. The integrality of αn+β\alpha n+\beta, together with n≡1(mod3)n\equiv1\pmod3 and (29), forces β=−1/3\beta=-1/3 or 1/31/3, respectively. These give (30) with a0=1a_0=1.

One active coordinate. Suppose only the coordinate jj is active. Negating the character and β\beta preserves the hypothesis, so assume δj=1/d\delta_j=1/d, where d=djd=d_j and a=5da=5d. We may take cj=(1−d)/15c_j=(1-d)/15, because d≡1(mod15)d\equiv1\pmod{15} and 15cj≡1(modd)15c_j\equiv1\pmod d. Write m=(d−1)/3m=(d-1)/3. The first phase of block hh is

Ph≡2u3+(3v−1)(2+3h)15+2+3h15d(mod1).(33)P_h \equiv\frac{2u}{3}+\frac{(3v-1)(2+3h)}{15}+\frac{2+3h}{15d}\pmod1. \tag*{(33)}

Each block is a progression with step 1/d1/d. Its width is m/dm/d when h=0h=0 and (m−1)/d(m-1)/d otherwise. Since all blocks lie in II, their first phases have representatives in an interval of width at most

13−m−1d=43d.\frac{1}{3}-\frac{m-1}{d}=\frac{4}{3d}.

Successive first phases differ modulo one by (3v−1)/5+1/(5d)(3v-1)/5+1/(5d). Unless v=2v=2 modulo 55, its distance from an integer is at least 1/5−1/(5d)>4/(3d)1/5-1/(5d)>4/(3d), because d>8d>8. Hence v=2v=2.

The first phases then advance by 1/(5d)1/(5d). The h=0h=0 block contains the real range of all five blocks because the other starts are shifted forward by at most 4/(5d)4/(5d) and their widths are smaller by 1/d1/d. Its initial phase is 2u/3+2/3+2/(15d)2u/3+2/3+2/(15d) modulo one. Containment in BB forces u=1u=1 modulo 33: u=0u=0 starts above 2/32/3, and u=2u=2 below 1/31/3. The full range of phases is therefore

[13+23a,23−23a,23+1a].(34)\left[\frac{1}{3}+\frac{2}{3a},\frac{2}{3}-\frac{2}{3a},\frac{2}{3}+\frac{1}{a}\right]. \tag*{(34)}

Its translates by βx\beta x stay in BB only if

−23a≤β≤1a.(35)-\frac{2}{3a}\le\beta\le\frac{1}{a}. \tag*{(35)}

Using κj≡6(mod15)\kappa_j \equiv6 \pmod{15}, formula (31) now simplifies to

α≡13+κj3a(mod1).(36)\alpha\equiv\frac{1}{3}+\frac{\kappa_j}{3a}\pmod{1}. \tag*{(36)}

Indeed, 2/5+(1−d)κj/(15d)2/5+(1-d)\kappa_j/(15d) is congruent to κj/(15d)\kappa_j/(15d). The number

(13+κj3a)n+13a=(a+κj)n+13a(37)\left(\frac{1}{3}+\frac{\kappa_j}{3a}\right)n+\frac{1}{3a}=\frac{(a+\kappa_j)n+1}{3a} \tag*{(37)}

is integral, since its numerator is divisible by aa by (18) and by 3 by (14) and (17). The interval (35) has length 5/(3a)<15/(3a)<1 and contains 1/(3a)1/(3a). Thus integrality leaves precisely β=1/(3a)\beta=1/(3a). Multiplying (37) by 3a3a shows that 3Ka≡1(modn)3Ka\equiv1\pmod n. As n≡1(mod3)n\equiv1\pmod3, this gives Ka≡(2n+1)/3≡−(n−1)/3(modn)Ka\equiv(2n+1)/3\equiv-(n-1)/3\pmod n. Negation covers the other sign. □

From finite deficits to exact rigidity

We now prove Condition (iv) with the finite size bound (19). No compactness or limiting argument is needed.

Proposition 6.1. For the parameters above, F(K)≤rF(K)\le r implies (30) for some ii. In particular DK(ai)=1>0D_K(a_i)=1>0. Proof. Each individual deficit is at most rr. By symmetry in ss and −s-s, every s∈Ss\in S satisfies

[Ks]nn∈Bε=[13−ε,23+ε],ε=r3n.(38)\frac{[Ks]_n}{n}\in B_\varepsilon=\left[\frac{1}{3}-\varepsilon,\frac{2}{3}+\varepsilon\right],\qquad\varepsilon=\frac{r}{3n}. \tag*{(38)}

The width w=1/3+2εw=1/3+2\varepsilon is less than 1/21/2. Choose a residue class in R\mathcal{R} not containing the possible involution n/2n/2. Its positive representatives below nn form an uninterrupted progression of step LL, with at least n/L−1n/L-1 elements. The phases of consecutive representatives have differences in [−w,w][-w,w] and are all congruent to KL/nKL/n modulo one. Since 2w<12w<1, these real differences are equal. Write their common value as δ=KL/n−p\delta=KL/n-p, where p∈Zp\in\mathbb{Z}. Telescoping gives ∣δ∣(n/L−2)≤w|\delta|(n/L-2)\le w. Set α=p/L\alpha=p/L and β=nδ/L\beta=n\delta/L. Then K=αn+βK=\alpha n+\beta, and (19) gives

∣β∣≤w1−2L/n<12.(39)|\beta|\le\frac{w}{1-2L/n}<\frac{1}{2}. \tag*{(39)}

For an arbitrary ρ∈R\rho\in\mathcal{R}, its first and last positive representatives below nn lie within LL of 0 and nn, respectively. Neither is the involution, since n>2Ln>2L. Their phases in (38) show that αρ\alpha\rho and αρ+β\alpha\rho+\beta have circular distance from BB at most

ε+∣β∣Ln<r/3+L/2n<1L.(40)\varepsilon+|\beta|\frac{L}{n}<\frac{r/3+L/2}{n}<\frac{1}{L}. \tag*{(40)}

Both phases belong to the grid L−1Z/ZL^{-1}\mathbb{Z}/\mathbb{Z}, because α=p/L\alpha=p/L and β=K−pn/L\beta=K-pn/L. The endpoints of BB belong to the same grid since 3∣L3\mid L. A grid point outside BB is at distance at least 1/L1/L from BB, so both phases actually belong to BB.

Their representatives in BB differ by at most 1/31/3. By (39) that difference must equal β\beta, since any nonzero integer shift of β\beta has magnitude greater than 1/21/2. The interpolating segment stays in BB, proving the hypothesis of Lemma 5.1. This yields (30). If m=(n−1)/3m=(n-1)/3, then min⁡(m,n−m)=m\min(m,n-m)=m and n−3m=1n-3m=1, so the resulting deficit is exactly one. □

Disjoint three-step words

We finish the construction by proving Condition (iii). Fix z∈Jz\in J, so 0<z<n/20<z<n/2. As S⊆NnS\subseteq N_n, either z=1z=1 or z≡2(mod3)z\equiv2\pmod3. If zz is nongeneric, it is one of the positive orientations aja_j, because every negative orientation exceeds n/2n/2 by the parameter bounds. Set

W=z+cn,c={2,z=1,1,z≠1.(41)W=z+cn,\qquad c=\begin{cases}2,&z=1,\\1,&z\ne1.\end{cases} \tag*{(41)}

Thus n<W≤2n+1n < W \le2n + 1 and W≡0(mod3)W \equiv0 \pmod{3}.

For each j≥1j \ge1, prescribe the sum of three eje_j coordinates as

Mj={aj+κj−2,z=1,2aj−1,z=aj,aj+ej(z)−1,otherwise.(42)M_j = \begin{cases} a_j + \kappa_j - 2, & z = 1,\\ 2a_j - 1, & z = a_j,\\ a_j + e_j(z) - 1, & \text{otherwise}. \end{cases} \tag*{(42)}

In the last case ej(z)≡2(mod3)e_j(z) \equiv2 \pmod{3}: for a generic zz this is the definition, and for another orientation it follows from compatibility and (25). In all cases

Mj≡0(mod3),aj<Mj<2aj,Mj≡z−c(mod5),Mj≡κjW(modaj).(43)M_j \equiv0 \pmod{3}, \qquad a_j < M_j < 2a_j, \qquad M_j \equiv z-c \pmod{5}, \qquad M_j \equiv\kappa_j W \pmod{a_j}. \tag*{(43)}

These follow directly from aj≡2(mod3)a_j \equiv2 \pmod{3}, κj≡6(mod15)\kappa_j \equiv6 \pmod{15}, and κjn≡−1(modaj)\kappa_j n \equiv-1 \pmod{a_j}.

For an explicit choice, put

Ej=2+15⌊Mj/3−215⌋,Ej1=Ej2=Ej,Ej3=Mj−2Ej.(44)E_j = 2 + 15\left\lfloor\frac{M_j/3 - 2}{15}\right\rfloor, \qquad E_j^1 = E_j^2 = E_j, \qquad E_j^3 = M_j - 2E_j. \tag*{(44)}

Writing bj=Mj/3−Ejb_j = M_j/3 - E_j, we have 0≤bj≤140 \le b_j \le14 and Ej3=Mj/3+2bjE_j^3 = M_j/3 + 2b_j. Since aj>100a_j > 100 and aj<Mj<2aja_j < M_j < 2a_j, we obtain Ej>aj/3−14>0E_j > a_j/3 - 14 > 0 and 0<Ej3<2aj/3+28<aj0 < E_j^3 < 2a_j/3 + 28 < a_j. Also Ej<2aj/3<ajE_j < 2a_j/3 < a_j. All three coordinates are 2 modulo 3. Their residues modulo 5 are 2, 2, z−c−4z-c-4, independently of jj.

For each ℓ=1,2,3\ell= 1,2,3, the Chinese remainder theorem therefore gives a generic class ρℓ\rho_\ell modulo LL with these eje_j coordinates and residue 2 modulo 3. (43) implies

ρ1+ρ2+ρ3≡W(modL).(45)\rho_1 + \rho_2 + \rho_3 \equiv W \pmod{L}. \tag*{(45)}

Choose s1,s2s_1,s_2 in the first two classes, respectively, in the real interval

[W3−n24,W3+n24],(46)\left[\frac{W}{3} - \frac{n}{24},\frac{W}{3} + \frac{n}{24}\right], \tag*{(46)}

and set s3=W−s1−s2s_3 = W-s_1-s_2. Then s3s_3 belongs to the third class and lies within n/12n/12 of W/3W/3. All three integers lie strictly between 0 and nn. Each of the first two choices has at least n/(12L)−1n/(12L)-1 possibilities.

Lemma 7.1 (Uniform avoidance). For every set F⊆Z/nZF \subseteq\mathbb{Z}/n\mathbb{Z} with ∣F∣≤6r+2|F| \le6r+2, there is a three-step word summing to zz, using directions in SS and avoiding FF.

Proof. Add the possible involution to FF, obtaining a forbidden set of size at most 6r+36r+3. Choose s1s_1 outside it. Once s1s_1 is fixed, at most 2(6r+3)2(6r+3) values of s2s_2 are excluded by requiring both s2s_2 and W−s1−s2W-s_1-s_2 to avoid it. The bound on nn implies n/(12L)−1>2(6r+3)n/(12L)-1 > 2(6r+3), so both choices can be made. The three summands are generic and avoid the involution, hence lie in SS. Their sum is W≡z(modn)W \equiv z \pmod{n}, as required. □

Initially forbid zz and −z-z. After choosing a word, also forbid both signs of each of its three directions. Before the rrth choice there are at most 2+6(r−1)2+6(r-1) forbidden residues, so Lemma 7.1 applies at every stage. The resulting rr words avoid the target pair and have mutually disjoint sets of direction pairs. This proves Condition (iii).

Proof of Theorem 1.1. Lemma 3.1 and the subsequent CRT choice supply the integer parameters for every r≥1r \ge1. Define SS by (24) and add the chords (4). Lemma 3.2 and the discussion in Section 4 prove Conditions (i) and (ii). Proposition 6.1 proves Condition (iv), and the preceding word construction proves Condition (iii). Theorem 2.1 gives a finite (4,r)(4,r)-graph. □

Lean verification and computational checks

The original formal development was supplied as a single file, Solution.lean, with the two imports requested by the challenge:

import FormalConjectures.ErdosProblems.«944»
import TaskSupport

The code uses the namespace 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 propext, Classical.choice, and Quot.sound. None uses sorryAx. Reading the challenge theorem’s type with the supplied elaborator does not use that theorem as a proof.

The complete target

The original file contains 9,548 lines, including every supporting proof and the following final theorem in the namespace Bounty:

theorem target : fcTypeOfName% "Erdos944.erdos_944" := by
  constructor
  · intro _ k hk r _hr
    exact Erdos944Proof.erdos944_all hk r
  · intro _
    trivial

The audit driver separately checks that its type is

True⟺∀k≥4 ∀r≥1 ∃V ∃G,G has the Erdo˝s 944 property for k,r.\mathrm{True} \mathrel{\Longleftrightarrow} \forall k \ge4 \ \forall r \ge1 \ \exists V \ \exists G,\quad G\text{ has the Erdős 944 property for }k,r.

It also applies the theorem directly to this explicit proposition. The three existence lemmas are erdos944_four, erdos944_five, and erdos944_ge_six. They have no additional mathematical hypotheses, and also cover r=0r = 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 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 KLKL as an integer multiple of nn 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≥5k \ge5, the theorem higher_punctured proves the vertex-deleted colorings for every positive mm and natural qq. The row formula handles both parities of kk. Equal-colored vertices have restricted index differences, which avoid all three distance families in both cyclic directions. These definitions and colorings follow Skottová and Steiner [1 Section 4 and Appendix A]. The proof also bounds the affected vertices by twice the number of monochromatic edges. Dividing a window into 2r+12r+1 disjoint blocks then produces an unaffected block of length 3nk,m3n_{k,m}. Local propagation from such a block is proved below and then converted into the required graph property.

The theorem higher_clean_block_periodic proves periodicity inside every unaffected block of three periods, for all k≥5k \ge5, including k=6k = 6 and k=8k = 8. Odd kk uses a partition into cliques. Even kk uses ten-vertex subgraphs of independence number two and an interval-counting argument. This formalizes the local-periodicity claim of Skottová and Steiner [1 Claim 4.4]. The periodic expected coloring retains the block’s exact color counts and short-distance constraints. A color class larger than 2r2r in an interval of length 2m2m has a single parity: it contains an unaffected vertex, which excludes the opposite parity. Finally, for odd k≥5k \ge5, the unaffected prefix leaves only the expected colors at ii and i−1i-1 as options at later indices i<(q/2)nk,mi < (q/2)n_{k,m}. The even-color restriction and extension through the larger window are also proved.

The theorem higher_expected_local_structure_all establishes the local color structure for every k≥6k \ge6: on each parity, changes of expected color occur at exactly one residue modulo 2m2m. For odd k≥7k \ge7, each expected color class is one even-step block repeated periodically. For even k≥10k \ge10, it is two such blocks. The exceptional cases k=6,8k = 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 2m2m. Ring injectivity and an exact count of changes then give one change on each parity per period. These arguments formalize Skottová and Steiner [1 Claims 4.6–4.7 and Appendix B], using finite certificates checked by Lean’s kernel.

Completing propagation

Write L=nk,mL = n_{k,m} for the period of the expected coloring and take q=24r+12q = 24r + 12, so the graph has order qL+1qL + 1. We use m=18r+3m = 18r + 3 for k≥6k \ge6 and m=18r+20m = 18r + 20 for k=5k = 5. A coloring with at most rr bad edges has at most 2r2r affected vertices. A color occurring more than 2r2r times in any interval of length 2m2m therefore occurs at only one parity in that interval.

For even kk, put n=k−1n = k - 1 and s=⌊n/2⌋s = \lfloor n/2 \rfloor. Two adjacent rings have positions 2ma+b2ma + b, where 0≤a<n0 \le a < n and b∈{0,1}b \in\{0,1\}. Two distinct positions are adjacent whenever their row distance is neither ss nor s+1s + 1. Any three positions contain an edge: three distinct rows cannot have all three pairwise distances in {s,s+1}\{s,s + 1\} when s≥2s \ge2, and two positions in one row are adjacent. Thus every color occurs at most twice and, by counting 2n2n positions in nn colors, exactly twice. For a later vertex, the distance conditions exclude every row except 0,s,s+10,s,s + 1. The positions in rows s,s+1s,s + 1 form a clique, so the two occurrences of its color cannot both lie there. One occurs in row zero, giving the two expected-color options at indices ii and i−1i - 1. This proves the restriction for every even k≥6k \ge6 at once.

For k≥6k \ge6, suppose the first deviation from the expected coloring occurs at ii. The two options force its color to equal the preceding color. The even-run structure supplies a nearby interval of mm consecutive positions with only this color and one other color available. The repeated color occurs at both parities in a containing 2m2m-interval, so it occurs at most 2r2r times there. The other color must then occur at least m−2rm - 2r times in the mm-interval. It exceeds 2r2r, and the single-parity property bounds its count by ⌈m/2⌉\lceil m/2 \rceil. These inequalities contradict m≥4r+3m \ge4r + 3.

For k=5k = 5, write eje_j for the expected color and cjc_j for the actual color. The period is 4m4m. Every expected color occurs exactly mm times per period. Opposite parities use disjoint colors, and the two colors on the parity of aa are eae_a and ea+2me_{a+2m}. At a first deviation ii, set

γ=ei−1=ci−1=ci,δ=ei−2=ci−2,ε=ei−2+2m.\gamma= e_{i-1} = c_{i-1} = c_i,\qquad\delta= e_{i-2} = c_{i-2},\qquad\varepsilon= e_{i-2+2m}.

Let I=[i−2m+1,i]I = [i - 2m + 1,i] and J=[i−2,i+2m−3]J = [i - 2,i + 2m - 3], and let A,BA,B be the numbers of expected colors γ,ε\gamma,\varepsilon, respectively, in JJ. The actual color γ\gamma occurs at both parities in each interval, so its count in each is at most 2r2r. On II the expected γ\gamma-count is no larger than the actual count. The two intervals cover 4m−34m - 3 positions. The missing three positions in a 4m4m-window give

A≥m−2r−3(47)A \ge m - 2r - 3 \tag*{(47)}

In JJ, at most 2r2r occurrences of δ\delta can be at the parity opposite i−2i - 2. Otherwise the single-parity rule contradicts ci−2=δc_{i-2} = \delta. At a position with expected color γ\gamma, the two available colors force the actual color to be γ\gamma, δ\delta, or the preceding expected color ε\varepsilon. Shifting a color count by one changes it by at most one. Consequently

A≤4r+B+1.(48)A \le4r + B + 1. \tag*{(48)}

Let Cγ,CεC_\gamma,C_\varepsilon denote the actual counts in JJ. At each position, the number of occurrences of γ,ε\gamma,\varepsilon among the two expected options is at most one plus the indicator that the actual color lies in {γ,ε}\{\gamma,\varepsilon\}. Summing, and allowing one boundary error for each expected color, gives

2A+2B−2≤2m+Cγ+Cε.2A + 2B - 2 \le2m + C_\gamma+ C_\varepsilon.

Together with {(47)–(48)} and Cγ≤2rC_\gamma\le2r, this implies Cε≥2m−18r−16>mC_\varepsilon\ge2m - 18r - 16 > m. But every actual color in a 2m2m-interval occurs at most mm times: a count at most 2r2r is already bounded by mm, and a larger count has a single parity. This contradiction excludes the first deviation for k=5k = 5.

Thus a clean prefix determines the actual coloring throughout the required larger window. Every interval of length (6r+3)L(6r + 3)L contains a clean 3L3L-block. Reflecting that block and applying prefix agreement proves c(v+L)=c(v)c(v + L) = c(v) for every vertex vv. Since gcd⁡(L,qL+1)=1\gcd(L, qL + 1) = 1, such a coloring is constant, contradicting a proper edge in the clean block. Every (k−1)(k - 1)-coloring therefore has more than rr bad edges. Combining this with the punctured colorings proves the higher-color existence theorems and completes Bounty.target.

The main correspondences are listed below. Names are relative to Bounty.Erdos944Proof, except the final target.

Mathematical componentLean theorem
Punctured colorings of the augmented graphaugmentedGraph_punctured
Filled Hamiltonian gapsaugmentedGraph_filled_gaps
Height character for any unitexists_group_flux_character
Deficit estimate with retained liftsexists_character_with_lifts
Winding inductionandrasfai_cycle_flux_le
Two-sided gap boundpath_gain_bounds_of_badEdges_bound
Flux bound from all gapsflux_bounds_of_andrasfai_gaps
The graph construction criterionerdos944_four_of_cyclic_data
Short compatibility of constructed unitscyclic_data_shortCompatible
Disjoint words from avoidancehasSignedWords_of_avoidance
Transport to arbitrary universeserdos944_universe_lift
Arbitrarily large finite CRT solutionsexists_large_crt
Choice of q=3t+1q = 3t + 1 coprime to 15exists_gap_parameter
Canonical deficit equal to onecanonical_deficit_one
Recursive integer data for every rrexists_cyclic_integer_data
Exact normalized-coordinate formulanormalized_coordinate_mul
Unique five-block CRT gridexistsUnique_generic_grid_class
Generic residues give signed connectionscyclic_data_generic_signed_mem
Avoiding a finite set in a progressionexists_progression_point_avoiding
Splitting a coordinate sum into threesplit_three_residue_coordinates
Uniform three-step word avoidancecyclic_data_word_avoidance
Finite rounding to an exact charactercyclic_data_rounded_character
Affine phases on a CRT blockmiddleThirdCharacter_grid_affine
Sparsity of the CRT coefficientsmiddleThirdCharacter_sparse_coefficients
Exact periodic character rigiditycyclic_data_periodic_rigidity
Four-color existence for every rrerdos944_four
Higher-color punctured coloringshigher_punctured
An unaffected consecutive blockhigher_exists_unaffected_block
Local periodicity for every k≥5k \ge5higher_clean_block_periodic
Periodic expected-color countshigherExpectedColor_window_count
Parity of large short color classeshigher_short_color_class_single_parity
Two color options for odd kkhigher_odd_clean_prefix_two_options
Local color structure for every k≥6k \ge6higher_expected_local_structure_all
Injective rings for k=6,8k = 6, 8higher_small_ring_color_injective
Reduction to local propagationhigher_erdos944_of_local_propagation
Two color options for even kkhigher_even_clean_prefix_two_options
First-deviation count for k=5k = 5five_first_deviation_impossible
Existence for k=5k = 5erdos944_five
Existence for every k≥6k \ge6erdos944_ge_six
All-color existenceerdos944_all

Table 1.

Mathematical componentLean theorem
Exact challenge propositionBounty.target

Pinned environment

The original checked environment used the following revisions. Its validation.json recorded the exact source hash and audit results.

  • Lean compiler: 819816b2e0a3bf405af45ae5c7af2491d8f5bee6.

  • Formal Conjectures audited revision: 8432eac998110a563e03df65a28c117e97c8c142.

  • mathlib revision [4]: 0df444a360eaa60ab8c11dca51a86af692955474.

The challenge source uses 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 pinned reproducible prize package links the historical and accepted sources and checks the explicit finite target. Its recorded clean target build and axiom audit covers 2,339 declarations using cached dependencies. The separate Conjectures verification record applies to the accepted challenge source. The source history distinguishes these versions from one another and from the original manuscript snapshot.

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.

rrqqDigits of nnDigits of LLWords checked
14783816
2771435538
31350,22025,10875

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.

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 8 records what Lean has verified, the source correspondence, and the pinned environment.

References

  1. [1]F. Skottová and R. Steiner, Critical edge sets in vertex-critical graphs, preprint, arXiv:2508.08703 (2025), https://arxiv.org/abs/2508.08703.
  2. [2]The Formal Conjectures Authors, Formal Conjectures, FormalConjectures/ErdosProblems/944.lean, https://github.com/google-deepmind/formal-conjectures.
  3. [3]Conjectures.io, Erdős 944 formalized challenge, https://conjectures.io/problems/erdos944-erdos-944/challenge?mode=formalized, accessed September 10, 2026.
  4. [4]The mathlib Community, mathlib4, https://github.com/leanprover-community/mathlib4.

Paper details

vlnc:W_5zh8atxy
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents