Erdős Problem #811

Erdős Problem 811 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/811.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT.

Let $m\ge 1$ and $n\ge 2$. An edge-coloring of $K_n$ using exactly $m$ colors is called balanced if every vertex is incident to exactly $\lfloor n/m\rfloor$ edges of each color.

Ambiguity / existence condition. If $n\equiv 1\pmod m$ then $\lfloor n/m\rfloor=(n-1)/m=:q$ is an integer and the vertex-degree condition becomes "each vertex has degree $q$ in each color class". However this forces each color class to have exactly $nq/2$ edges, so a necessary condition for existence is that $nq$ is even (equivalently $m\mid \binom{n}{2}$). If $nq$ is odd, no balanced coloring exists and statements about "every balanced coloring" are vacuous.

Now fix a finite simple graph $G$ and let $m:=e(G)$. Question: For which graphs $G$ is it true that for all sufficiently large $n$ with $m\mid (n-1)$ and for which balanced $m$-colorings of $K_n$ exist, every balanced $m$-edge-coloring of $K_n$ contains a rainbow copy of $G$ (a copy of $G$ whose $m$ edges all have distinct colors)?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem text reports that Erdős--Tuza studied this and obtained bounds for a quantitative variant, and that recent work shows infinitely many graphs fail the property; in particular it says $K_4$ lacks the property. I do not use results beyond what is written in the problem text.

3) ATTACK PLAN.

Proof strategies for positive cases.

• Translate a rainbow-copy search into a system of distinct representatives (SDR) problem using the regularity of each color class; apply Hall-type arguments for graphs $G$ with bounded structure (stars, matchings, trees).
• Use greedy embedding: order the edges of $G$ and embed them one-by-one, using that each vertex has many available edges in each color.

Disproof strategies / negative cases.

• Construct balanced colorings from structured decompositions of $K_n$ into regular spanning subgraphs that avoid certain rainbow patterns (e.g. avoiding rainbow cliques).
• Look for parity/degree obstructions and exploit high symmetry (e.g. group-based colorings) to forbid rainbow embeddings.

I do not classify all $G$; the work below proves two basic structural lemmas and one unconditional positive result for stars when $n$ is large compared to $m$.

4) WORK.

Lemma 811.1 (structure of balanced colorings). Assume $m\mid (n-1)$ and set $q:=(n-1)/m$. If $\chi$ is a balanced edge-coloring of $K_n$ with $m$ colors, then for each color $c$ the color class $H_c$ (the spanning subgraph of edges colored $c$) is $q$-regular and has exactly $\frac{nq}{2}$ edges. In particular, a necessary condition for existence of a balanced coloring is that $nq$ is even.

Proof. By balance, every vertex of $K_n$ is incident to exactly $q$ edges of color $c$, so $H_c$ is $q$-regular on the full vertex set. Summing degrees in $H_c$ gives $\sum_{v} d_{H_c}(v)=nq$, which equals $2|E(H_c)|$ by the handshake lemma, hence $|E(H_c)|=nq/2$. Therefore $nq$ must be even for $|E(H_c)|$ to be an integer. $\square$

Lemma 811.2 (rainbow stars for large $n$). Let $G$ be the star $K_{1,m}$, so $e(G)=m$. Assume $m\mid (n-1)$ and let $q=(n-1)/m$. If $q\ge m$ and $\chi$ is any balanced edge-coloring of $K_n$ with $m$ colors, then $K_n$ contains a rainbow copy of $K_{1,m}$.

Proof. Fix any vertex $v$ of $K_n$ as a candidate center. For each color $c\in[m]$, let $N_c(v)$ be the set of neighbors $u$ such that edge $vu$ has color $c$. By balance, $|N_c(v)|=q$ for every color $c$.

We seek distinct neighbors $u_c\in N_c(v)$ for all $c\in[m]$; then edges $vu_c$ form a rainbow $K_{1,m}$. This is a system of distinct representatives (SDR) problem for the family of sets $\{N_c(v)\}_{c\in[m]}$. By Hall's marriage theorem it suffices to check: for every subset $S\subseteq [m]$, \[ \left|\bigcup_{c\in S} N_c(v)\right|\ge |S|. \] But for any nonempty $S$, the union size is at least the maximum of the individual sizes, so \[ \left|\bigcup_{c\in S} N_c(v)\right|\ge \max_{c\in S}|N_c(v)|=q. \] If $q\ge m$ then for all $S\subseteq [m]$ we have $q\ge m\ge |S|$, hence Hall's condition holds. Therefore an SDR exists, giving distinct neighbors $u_c$ and thus a rainbow $K_{1,m}$ centered at $v$. $\square$

FAST REALITY CHECK (existence/parity). For $m=6$ and $n=7$ (the smallest $n\equiv 1\pmod 6$), we have $q=(n-1)/m=1$ and thus $nq=7$ is odd. By Lemma 811.1, no balanced $6$-coloring of $K_7$ exists. More generally, when $m$ is even and $q$ is odd, balanced colorings cannot exist because each color class would have $nq/2$ edges with $n$ odd.

5) VERIFICATION.

• Lemma 811.1: the only nontrivial check is integrality; degree sum $nq$ must be even.
• Lemma 811.2: verified Hall's condition carefully. The worst-case union size is $q$ (when all $N_c(v)$ coincide), and the assumed condition $q\ge m$ exactly forces $q\ge |S|$ for every $S\subseteq[m]$.
• The star embedding indeed gives a rainbow copy because each edge uses a different color by construction.

6) FINAL. UNRESOLVED.

1. (i) Strongest proved partial result here: balanced $m$-colorings (when they exist) decompose $K_n$ into $m$ spanning $q$-regular graphs (Lemma 811.1). For the special case $G=K_{1,m}$, if $n\ge m^2+1$ (so $q=(n-1)/m\ge m$), then every balanced coloring contains a rainbow copy of $G$ (Lemma 811.2).
2. (ii) First gap (crisp): determine for which non-star graphs $G$ (in particular cliques such as $K_4$ or cycles such as $C_6$) every balanced $e(G)$-coloring of $K_n$ (for large admissible $n$) must contain a rainbow copy of $G$.
3. (iii) Top 3 next moves:
   1. Extend the SDR/Hall approach from stars to matchings and small trees: prove that for fixed $G$ a rainbow embedding exists whenever $q$ exceeds an explicit function of $|V(G)|$ and $\Delta(G)$.
   2. Attempt a general "rainbow blow-up lemma" style greedy embedding: order edges of $G$ and keep track of forbidden colors/vertices, using the $q$-regularity of each color class.
   3. For specific targets ($C_6$, $K_4$), search for explicit balanced colorings on the smallest admissible $n$ using SAT/ILP to see the shape of obstructions.
4. (iv) What a minimal counterexample would likely look like: a balanced coloring in which the $m$ regular color classes are highly structured (e.g. arising from a group action or a design) so that any attempt to choose $m$ edges with distinct colors forces unwanted vertex collisions, preventing a rainbow copy of the target $G$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

1) FORMAL RESTATEMENT.

Let $m\ge 1$ and $n\ge 2$. An edge-coloring of $K_n$ using exactly $m$ colors is called balanced if every vertex is incident to exactly $\lfloor n/m\rfloor$ edges of each color.

Ambiguity / existence condition. If $n\equiv 1\pmod m$ then $\lfloor n/m\rfloor=(n-1)/m=:q$ is an integer and the vertex-degree condition becomes "each vertex has degree $q$ in each color class". However this forces each color class to have exactly $nq/2$ edges, so a necessary condition for existence is that $nq$ is even (equivalently $m\mid \binom{n}{2}$). If $nq$ is odd, no balanced coloring exists and statements about "every balanced coloring" are vacuous.

Now fix a finite simple graph $G$ and let $m:=e(G)$. Question: For which graphs $G$ is it true that for all sufficiently large $n$ with $m\mid (n-1)$ and for which balanced $m$-colorings of $K_n$ exist, every balanced $m$-edge-coloring of $K_n$ contains a rainbow copy of $G$ (a copy of $G$ whose $m$ edges all have distinct colors)?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem text reports that Erdős--Tuza studied this and obtained bounds for a quantitative variant, and that recent work shows infinitely many graphs fail the property; in particular it says $K_4$ lacks the property. I do not use results beyond what is written in the problem text.

3) ATTACK PLAN.

Proof strategies for positive cases.

• Translate a rainbow-copy search into a system of distinct representatives (SDR) problem using the regularity of each color class; apply Hall-type arguments for graphs $G$ with bounded structure (stars, matchings, trees).
• Use greedy embedding: order the edges of $G$ and embed them one-by-one, using that each vertex has many available edges in each color.

Disproof strategies / negative cases.

• Construct balanced colorings from structured decompositions of $K_n$ into regular spanning subgraphs that avoid certain rainbow patterns (e.g. avoiding rainbow cliques).
• Look for parity/degree obstructions and exploit high symmetry (e.g. group-based colorings) to forbid rainbow embeddings.

I do not classify all $G$; the work below proves two basic structural lemmas and one unconditional positive result for stars when $n$ is large compared to $m$.

4) WORK.

Lemma 811.1 (structure of balanced colorings). Assume $m\mid (n-1)$ and set $q:=(n-1)/m$. If $\chi$ is a balanced edge-coloring of $K_n$ with $m$ colors, then for each color $c$ the color class $H_c$ (the spanning subgraph of edges colored $c$) is $q$-regular and has exactly $\frac{nq}{2}$ edges. In particular, a necessary condition for existence of a balanced coloring is that $nq$ is even.

Proof. By balance, every vertex of $K_n$ is incident to exactly $q$ edges of color $c$, so $H_c$ is $q$-regular on the full vertex set. Summing degrees in $H_c$ gives $\sum_{v} d_{H_c}(v)=nq$, which equals $2|E(H_c)|$ by the handshake lemma, hence $|E(H_c)|=nq/2$. Therefore $nq$ must be even for $|E(H_c)|$ to be an integer. $\square$

Lemma 811.2 (rainbow stars for large $n$). Let $G$ be the star $K_{1,m}$, so $e(G)=m$. Assume $m\mid (n-1)$ and let $q=(n-1)/m$. If $q\ge m$ and $\chi$ is any balanced edge-coloring of $K_n$ with $m$ colors, then $K_n$ contains a rainbow copy of $K_{1,m}$.

Proof. Fix any vertex $v$ of $K_n$ as a candidate center. For each color $c\in[m]$, let $N_c(v)$ be the set of neighbors $u$ such that edge $vu$ has color $c$. By balance, $|N_c(v)|=q$ for every color $c$.

We seek distinct neighbors $u_c\in N_c(v)$ for all $c\in[m]$; then edges $vu_c$ form a rainbow $K_{1,m}$. This is a system of distinct representatives (SDR) problem for the family of sets $\{N_c(v)\}_{c\in[m]}$. By Hall's marriage theorem it suffices to check: for every subset $S\subseteq [m]$, \[ \left|\bigcup_{c\in S} N_c(v)\right|\ge |S|. \] But for any nonempty $S$, the union size is at least the maximum of the individual sizes, so \[ \left|\bigcup_{c\in S} N_c(v)\right|\ge \max_{c\in S}|N_c(v)|=q. \] If $q\ge m$ then for all $S\subseteq [m]$ we have $q\ge m\ge |S|$, hence Hall's condition holds. Therefore an SDR exists, giving distinct neighbors $u_c$ and thus a rainbow $K_{1,m}$ centered at $v$. $\square$

FAST REALITY CHECK (existence/parity). For $m=6$ and $n=7$ (the smallest $n\equiv 1\pmod 6$), we have $q=(n-1)/m=1$ and thus $nq=7$ is odd. By Lemma 811.1, no balanced $6$-coloring of $K_7$ exists. More generally, when $m$ is even and $q$ is odd, balanced colorings cannot exist because each color class would have $nq/2$ edges with $n$ odd.

5) VERIFICATION.

• Lemma 811.1: the only nontrivial check is integrality; degree sum $nq$ must be even.
• Lemma 811.2: verified Hall's condition carefully. The worst-case union size is $q$ (when all $N_c(v)$ coincide), and the assumed condition $q\ge m$ exactly forces $q\ge |S|$ for every $S\subseteq[m]$.
• The star embedding indeed gives a rainbow copy because each edge uses a different color by construction.

6) FINAL. UNRESOLVED.

1. (i) Strongest proved partial result here: balanced $m$-colorings (when they exist) decompose $K_n$ into $m$ spanning $q$-regular graphs (Lemma 811.1). For the special case $G=K_{1,m}$, if $n\ge m^2+1$ (so $q=(n-1)/m\ge m$), then every balanced coloring contains a rainbow copy of $G$ (Lemma 811.2).
2. (ii) First gap (crisp): determine for which non-star graphs $G$ (in particular cliques such as $K_4$ or cycles such as $C_6$) every balanced $e(G)$-coloring of $K_n$ (for large admissible $n$) must contain a rainbow copy of $G$.
3. (iii) Top 3 next moves:
   1. Extend the SDR/Hall approach from stars to matchings and small trees: prove that for fixed $G$ a rainbow embedding exists whenever $q$ exceeds an explicit function of $|V(G)|$ and $\Delta(G)$.
   2. Attempt a general "rainbow blow-up lemma" style greedy embedding: order edges of $G$ and keep track of forbidden colors/vertices, using the $q$-regularity of each color class.
   3. For specific targets ($C_6$, $K_4$), search for explicit balanced colorings on the smallest admissible $n$ using SAT/ILP to see the shape of obstructions.
4. (iv) What a minimal counterexample would likely look like: a balanced coloring in which the $m$ regular color classes are highly structured (e.g. arising from a group action or a design) so that any attempt to choose $m$ edges with distinct colors forces unwanted vertex collisions, preventing a rainbow copy of the target $G$.