WorksMathematics
Vertex-critical four-chromatic graphs with no small critical edge set
Abstract
For every positive integer , we construct a finite four-chromatic graph such that deleting any vertex lowers the chromatic number, and deleting any set of at most 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 -graph for a finite graph satisfying
The existence statement of Erdős problem 944 asks whether a -graph exists for every and . 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 and . Their result leaves the four-color case.
Theorem 1.1 (Construction). For every integer , there is a finite -graph.
Corollary 1.2. For every and , there is a finite -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 , 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 , with a paired-ring argument for even and an overlapping-interval count for . All witnesses are transported to the universe required by the challenge. The theorem Bounty.target proves exactly the displayed proposition for every and . Section 8 gives the proof correspondence and pinned verification environment. The symbolic proof is independent of the supplementary finite computations.
Notation
For an integer and a positive integer , write for the least nonnegative residue of modulo . We identify elements of with their least representatives when inequalities or residues modulo 3 are used. A direction pair is an unordered pair in . If is an inverse-closed set of nonzero directions, has the edges for . 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 and put
Fix , , and , with and . Let be units modulo with distinct direction pairs. Let be inverse-closed, contain all , and contain neither zero nor an element of order two. Let . Thus contains exactly one representative of every direction pair in . For , define
The deficit is unchanged when or is negated.
Theorem 2.1 (Construction criterion). Suppose the following conditions hold.
(i) for every .
(ii) For and , .
(iii) Every is the sum of each of three-step words in . Their direction pairs avoid and the sets of direction pairs used by different words are disjoint.
(iv) If , then for some .
Start with . For each , and every vertex with , add the edges
Identify repeated edges. The resulting simple graph is a -graph.
Punctured colorings
Delete a vertex , let , and color every remaining vertex by
If a normalized difference is 2 modulo 3, its color difference is 2 without a wrap and 1 with a wrap, since . Differences 1 and are also proper after coordinate zero is deleted. Condition (i) therefore makes every core edge proper.
For a chord of type , the normalized forward length is 1 modulo 3. The chord lies inside a -step gap between consecutive vertices whose residue modulo is . Such a gap has no vertex of that residue class in its interior because remains a unit modulo . The puncture 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 is three-colorable for every , and assigning one new color to shows that .
Height characters
For different colors , let be the unique element of congruent to modulo 3.
Lemma 2.2 (Height character). Let be an inverse-closed set of directions generating , and suppose its Cayley graph is properly three-colored. There is a character and a translation-invariant mean height increment for every oriented generator, satisfying
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 has mean congruent to modulo .
Proof. Choose representatives for the generator pairs and pull the coloring back under the map taking to . Give each oriented grid edge the increment of its endpoint colors. The sum around a square is even, divisible by , and between and . 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 on .
Write for the kernel of the map. For , the difference is divisible by . Its change when moves by a unit grid step is in and divisible by , so that difference is independent of . Denote it by . It is additive in and extends to a real linear functional , since has finite index. The period gives . Height parity and color congruence give
Hence takes integral values on . 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 . Translation permutes the starting vertices, and therefore averaging a word adds the signed generator means. The contribution of the constant is modulo for an odd word. □
Bad edges and the deficit bound
Suppose a three-coloring of has at most bad edges. A direction pair in is called bad if at least one of its translated edges is bad. There are at most such pairs, since different direction pairs have disjoint edge sets. As , one of the chosen unit directions has no bad edge. The remaining proper directions still generate .
If a target direction is bad, its words in Condition (iii) avoid its own pair. At most other bad pairs can spoil these mutually disjoint words, so at least one is wholly proper. If is proper, use the word instead. Apply Lemma 2.2 to the proper directions and let be the height increment of a selected three-step word for , starting at . It belongs to and has the endpoint color difference as its residue modulo . Consequently it is at a proper -edge and at a bad one. If is the number of bad -edges and is the mean of these word increments, then
There are exactly edges in this direction pair: the assumption that is not an involution makes injective. If , the least possible absolute value of a real number congruent to modulo is . (7) gives . Summing over the representatives in therefore proves
Moreover, forces .
The winding inequality
Let have vertex set and an edge , with , exactly when . In particular it contains the consecutive cycle edges, including the closing edge.
Lemma 2.3 (Winding bound). Suppose a three-coloring of has at most bad edges. Along the path , assign increments to proper edges and to bad edges, each congruent modulo to its color difference. The sum of the increments lies between and .
Proof. For a color pair define its maximal increment to be if the colors are equal, if the color increases by modulo , and otherwise. For a cyclic color word of length , let be the sum of these maximal increments. We prove by induction that at most bad edges imply .
For , the graph is a proper edge traversed in both directions, so . If and there are no bad cycle edges, then . Its parity agrees with and it is divisible by , giving .
Otherwise let be the number of bad cycle edges, so . The 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 , since and reversing an allowed cyclic difference again gives a difference modulo .
The remaining induced graph, in its cyclic order, is . At least the initial bad edge disappears. If is the sum of the following three proper increments, the four removed increments sum to . The maximal increment on the new bridge is, respectively, . Thus the old cycle sum is at most the new one plus . Induction proves .
The maximal path increments dominate the assigned increments. The closing increment is at least , so a path sum exceeding would give . 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 . If a three-coloring had at most bad edges, (8) and Condition (iv) would supply an with . Reverse the orientation if necessary. The sum of its word increments around its unit Hamiltonian cycle then exceeds . Partition the cycle into its designated gaps of length . Some gap has sum exceeding . Its vertices span by (4) and the unit core edges, contradicting Lemma 2.3, since the entire graph has at most bad edges. Reversal preserves the same gap graphs.
Thus every three-coloring of has more than bad edges. In particular is not three-colorable, so . A three-coloring after deleting at most edges would have at most bad edges in , which is impossible. Finally, cannot be at most , since adding in a new color would three-color . Therefore (1) holds with . □
The integer parameter construction
Fix . Choose unless , in which case choose . Then is coprime to . Put
For , recursively choose integers satisfying
Lemma 3.1. These choices exist. The are pairwise coprime, and for every $j\ge 1,
Proof. Every is 1 modulo . Since , it is also 1 modulo , and modulo by (11). Thus is coprime to both and . A common divisor of and divides . As , this proves .
For a new index , condition (13) is equivalent to
The moduli 3, , and the earlier are pairwise coprime. Indeed, , the are coprime to by the observations above, and their pairwise coprimality follows inductively from (13). The Chinese remainder theorem supplies an arithmetic progression of choices for . Take a sufficiently large member to satisfy (12).
Finally is divisible by 15, and is 0 modulo 3 and 1 modulo 5, proving the first two congruences in (14). The coprimality with follows from the coprimality with and . The two congruences for follow from and .
Set
Choose a positive integer with
Such integers form a nonempty progression of step . To see this, separate the common factor 5 of the . Their prescribed residues are all modulo 5, because . The remaining moduli are pairwise coprime and coprime to , while is coprime to 15. The Chinese remainder theorem therefore applies to , , 5, , and an arbitrarily large member may be chosen. For a deterministic choice, take the least member satisfying (19).
Each is a unit modulo , and its least positive inverse for is
The numerator is divisible by by (18). Since and is larger than all the parameters , the displayed quotient is strictly between 0 and .
Lemma 3.2 (Short compatible ratios). For all distinct indices ,
Consequently the have distinct direction pairs.
Proof. When , the representative is . Equation (14) and the size of give the result. Suppose and set . Equation (20) gives the integer representative
We check that it is less than , which also confirms that it is the least positive representative. If , then , and . If , condition (13) gives , again with . If , use
The fractional part is positive and less than . The integer part is . Thus in both cases , . For we instead have . Using and in (22) now gives in every case.
Since , the bound on implies . Equation (22) consequently gives when . This proves (21). Equality modulo would make their ratio , while would make it . Neither has residue modulo .
The core and its periodic residue classes
Define
where the last removal is made only when is even. The set is inverse-closed because the negative of a residue modulo has the same residue, since . Thus is inverse-closed and has no involution. Lemma 3.2 puts all in . It proves Conditions (i) and (ii) as well. For with , the product of with an off-diagonal ratio is less than and is modulo .
For and an integer , write . For , equation (20) yields the exact identity
The right side is a positive integer less than , because and .
Apart from the residues , membership in the intersection in (24) is equivalent to
Indeed, a normalized coordinate equals or only at the two corresponding orientations. Away from those exceptions, every normalized coordinate must be modulo . Equation (25), with , gives (26). Conversely those congruences make every coordinate modulo .
Call (26) the generic condition. It has period , independently of . Let be its residue classes. Every positive representative below of a class in belongs to , except the possible involution. The Chinese remainder theorem describes as five products. Put . For , impose
where the coordinates are independent and range over
To check this, use , so that and have the same residue modulo . The residue modulo fixes the least representative modulo as . Since , listing these representatives in gives exactly (28). The coordinates modulo , together with the residues modulo and , are independent CRT coordinates. Every block is nonempty, so in particular contains more than one class.
Exact character rigidity
Let . The following lemma is the arithmetic classification on which the construction rests.
then, for some ,
Proof. A continuous linear path contained in an arc of length has . Taking the two endpoints in (29) shows that all have real representatives in a common interval of width at most .
Decompose the character in the independent CRT coordinates:
with integer coefficients , taken modulo , respectively. In the product in (28), increasing by one changes the phase by modulo one. Since all real representatives lie in , their actual difference lies in . 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 . The phase on the product is therefore affine in its coordinates, and its width is
Each for an integer . Since , a nonzero must equal or . Moreover at most one can be nonzero, since two would contribute at least . Here all .
No active coordinate. If all vanish, then modulo , and the five block phases are , with running through . For modulo these are five equally spaced points, which cannot lie in . Thus , and or . The character is consequently or modulo one. The integrality of , together with and (29), forces or , respectively. These give (30) with .
One active coordinate. Suppose only the coordinate is active. Negating the character and preserves the hypothesis, so assume , where and . We may take , because and . Write . The first phase of block is
Each block is a progression with step . Its width is when and otherwise. Since all blocks lie in , their first phases have representatives in an interval of width at most
Successive first phases differ modulo one by . Unless modulo , its distance from an integer is at least , because . Hence .
The first phases then advance by . The block contains the real range of all five blocks because the other starts are shifted forward by at most and their widths are smaller by . Its initial phase is modulo one. Containment in forces modulo : starts above , and below . The full range of phases is therefore
Its translates by stay in only if
Using , formula (31) now simplifies to
Indeed, is congruent to . The number
is integral, since its numerator is divisible by by (18) and by 3 by (14) and (17). The interval (35) has length and contains . Thus integrality leaves precisely . Multiplying (37) by shows that . As , this gives . 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, implies (30) for some . In particular . Proof. Each individual deficit is at most . By symmetry in and , every satisfies
The width is less than . Choose a residue class in not containing the possible involution . Its positive representatives below form an uninterrupted progression of step , with at least elements. The phases of consecutive representatives have differences in and are all congruent to modulo one. Since , these real differences are equal. Write their common value as , where . Telescoping gives . Set and . Then , and (19) gives
For an arbitrary , its first and last positive representatives below lie within of 0 and , respectively. Neither is the involution, since . Their phases in (38) show that and have circular distance from at most
Both phases belong to the grid , because and . The endpoints of belong to the same grid since . A grid point outside is at distance at least from , so both phases actually belong to .
Their representatives in differ by at most . By (39) that difference must equal , since any nonzero integer shift of has magnitude greater than . The interpolating segment stays in , proving the hypothesis of Lemma 5.1. This yields (30). If , then and , so the resulting deficit is exactly one. □
Disjoint three-step words
We finish the construction by proving Condition (iii). Fix , so . As , either or . If is nongeneric, it is one of the positive orientations , because every negative orientation exceeds by the parameter bounds. Set
Thus and .
For each , prescribe the sum of three coordinates as
In the last case : for a generic this is the definition, and for another orientation it follows from compatibility and (25). In all cases
These follow directly from , , and .
For an explicit choice, put
Writing , we have and . Since and , we obtain and . Also . All three coordinates are 2 modulo 3. Their residues modulo 5 are 2, 2, , independently of .
For each , the Chinese remainder theorem therefore gives a generic class modulo with these coordinates and residue 2 modulo 3. (43) implies
Choose in the first two classes, respectively, in the real interval
and set . Then belongs to the third class and lies within of . All three integers lie strictly between 0 and . Each of the first two choices has at least possibilities.
Lemma 7.1 (Uniform avoidance). For every set with , there is a three-step word summing to , using directions in and avoiding .
Proof. Add the possible involution to , obtaining a forbidden set of size at most . Choose outside it. Once is fixed, at most values of are excluded by requiring both and to avoid it. The bound on implies , so both choices can be made. The three summands are generic and avoid the involution, hence lie in . Their sum is , as required. □
Initially forbid and . After choosing a word, also forbid both signs of each of its three directions. Before the th choice there are at most forbidden residues, so Lemma 7.1 applies at every stage. The resulting 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 . Define 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 -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
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 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 as an integer multiple of 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 , the theorem higher_punctured proves the vertex-deleted colorings for every positive and natural . The row formula handles both parities of . 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 disjoint blocks then produces an unaffected block of length . 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 , including and . Odd uses a partition into cliques. Even 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 in an interval of length has a single parity: it contains an unaffected vertex, which excludes the opposite parity. Finally, for odd , the unaffected prefix leaves only the expected colors at and as options at later indices . 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 : on each parity, changes of expected color occur at exactly one residue modulo . For odd , each expected color class is one even-step block repeated periodically. For even , it is two such blocks. The exceptional cases 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 . 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 for the period of the expected coloring and take , so the graph has order . We use for and for . A coloring with at most bad edges has at most affected vertices. A color occurring more than times in any interval of length therefore occurs at only one parity in that interval.
For even , put and . Two adjacent rings have positions , where and . Two distinct positions are adjacent whenever their row distance is neither nor . Any three positions contain an edge: three distinct rows cannot have all three pairwise distances in when , and two positions in one row are adjacent. Thus every color occurs at most twice and, by counting positions in colors, exactly twice. For a later vertex, the distance conditions exclude every row except . The positions in rows 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 and . This proves the restriction for every even at once.
For , suppose the first deviation from the expected coloring occurs at . The two options force its color to equal the preceding color. The even-run structure supplies a nearby interval of consecutive positions with only this color and one other color available. The repeated color occurs at both parities in a containing -interval, so it occurs at most times there. The other color must then occur at least times in the -interval. It exceeds , and the single-parity property bounds its count by . These inequalities contradict .
For , write for the expected color and for the actual color. The period is . Every expected color occurs exactly times per period. Opposite parities use disjoint colors, and the two colors on the parity of are and . At a first deviation , set
Let and , and let be the numbers of expected colors , respectively, in . The actual color occurs at both parities in each interval, so its count in each is at most . On the expected -count is no larger than the actual count. The two intervals cover positions. The missing three positions in a -window give
In , at most occurrences of can be at the parity opposite . Otherwise the single-parity rule contradicts . At a position with expected color , the two available colors force the actual color to be , , or the preceding expected color . Shifting a color count by one changes it by at most one. Consequently
Let denote the actual counts in . At each position, the number of occurrences of among the two expected options is at most one plus the indicator that the actual color lies in . Summing, and allowing one boundary error for each expected color, gives
Together with {(47)–(48)} and , this implies . But every actual color in a -interval occurs at most times: a count at most is already bounded by , and a larger count has a single parity. This contradiction excludes the first deviation for .
Thus a clean prefix determines the actual coloring throughout the required larger window. Every interval of length contains a clean -block. Reflecting that block and applying prefix agreement proves for every vertex . Since , such a coloring is constant, contradicting a proper edge in the clean block. Every -coloring therefore has more than 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 component | Lean theorem |
| Punctured colorings of the augmented graph | augmentedGraph_punctured |
| Filled Hamiltonian gaps | augmentedGraph_filled_gaps |
| Height character for any unit | exists_group_flux_character |
| Deficit estimate with retained lifts | exists_character_with_lifts |
| Winding induction | andrasfai_cycle_flux_le |
| Two-sided gap bound | path_gain_bounds_of_badEdges_bound |
| Flux bound from all gaps | flux_bounds_of_andrasfai_gaps |
| The graph construction criterion | erdos944_four_of_cyclic_data |
| Short compatibility of constructed units | cyclic_data_shortCompatible |
| Disjoint words from avoidance | hasSignedWords_of_avoidance |
| Transport to arbitrary universes | erdos944_universe_lift |
| Arbitrarily large finite CRT solutions | exists_large_crt |
| Choice of coprime to 15 | exists_gap_parameter |
| Canonical deficit equal to one | canonical_deficit_one |
| Recursive integer data for every | exists_cyclic_integer_data |
| Exact normalized-coordinate formula | normalized_coordinate_mul |
| Unique five-block CRT grid | existsUnique_generic_grid_class |
| Generic residues give signed connections | cyclic_data_generic_signed_mem |
| Avoiding a finite set in a progression | exists_progression_point_avoiding |
| Splitting a coordinate sum into three | split_three_residue_coordinates |
| Uniform three-step word avoidance | cyclic_data_word_avoidance |
| Finite rounding to an exact character | cyclic_data_rounded_character |
| Affine phases on a CRT block | middleThirdCharacter_grid_affine |
| Sparsity of the CRT coefficients | middleThirdCharacter_sparse_coefficients |
| Exact periodic character rigidity | cyclic_data_periodic_rigidity |
| Four-color existence for every | erdos944_four |
| Higher-color punctured colorings | higher_punctured |
| An unaffected consecutive block | higher_exists_unaffected_block |
| Local periodicity for every | higher_clean_block_periodic |
| Periodic expected-color counts | higherExpectedColor_window_count |
| Parity of large short color classes | higher_short_color_class_single_parity |
| Two color options for odd | higher_odd_clean_prefix_two_options |
| Local color structure for every | higher_expected_local_structure_all |
| Injective rings for | higher_small_ring_color_injective |
| Reduction to local propagation | higher_erdos944_of_local_propagation |
| Two color options for even | higher_even_clean_prefix_two_options |
| First-deviation count for | five_first_deviation_impossible |
| Existence for | erdos944_five |
| Existence for every | erdos944_ge_six |
| All-color existence | erdos944_all |
Table 1.
| Mathematical component | Lean theorem |
| Exact challenge proposition | Bounty.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.
| Digits of | Digits of | Words checked | ||
| 1 | 4 | 78 | 38 | 16 |
| 2 | 7 | 714 | 355 | 38 |
| 3 | 13 | 50,220 | 25,108 | 75 |
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]F. Skottová and R. Steiner, Critical edge sets in vertex-critical graphs, preprint, arXiv:2508.08703 (2025), https://arxiv.org/abs/2508.08703.
- [2]The Formal Conjectures Authors, Formal Conjectures, FormalConjectures/ErdosProblems/944.lean, https://github.com/google-deepmind/formal-conjectures.
- [3]Conjectures.io, Erdős 944 formalized challenge, https://conjectures.io/problems/erdos944-erdos-944/challenge?mode=formalized, accessed September 10, 2026.
- [4]The mathlib Community, mathlib4, https://github.com/leanprover-community/mathlib4.