Erdős Problem #596

Erdős Problem 596 --- 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/596.tex.

REUSED SOURCE 1

For which graphs $G_1,G_2$ is it true that {UL} {LI} for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet{/LI} {LI} for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$. {/UL} Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees). Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595] .

FORMAL RESTATEMENT

Fix finite graphs $G_1,G_2$. Consider the two properties:

1. $P1$ For every integer $n\ge 1$, there exists a graph $H$ which is $G_1$-free (contains no copy of $G_1$) such that for every edge-colouring $\kappa:E(H)\to[n]$ there exists a monochromatic copy of $G_2$ in $H$.
2. $P2$ For every $G_1$-free graph $H$, there exists an edge-colouring $\kappa:E(H)\to\omega$ such that $H$ has no monochromatic copy of $G_2$.

Problem: classify the pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. The statement notes that $(G_1,G_2)=(C_4,C_6)$ is such a pair.

QUICK LITERATURE/CONTEXT CHECK

I will not import external results beyond what is explicitly stated in the problem text. The text asserts that $(C_4,C_6)$ satisfies $P1$ (due to Nešetřil--Rödl) and $P2$ (due to Erdős--Hajnal), and even notes a strengthening: every $C_4$-free graph is a countable union of trees. The general classification problem is open-ended.

ATTACK PLAN

Understanding $P2$. Rewrite $P2$ as a countable decomposition problem: a countable edge-colouring avoiding monochromatic $G_2$ is the same as writing $E(H)$ as a countable union of $G_2$-free subgraphs. Seek structural reasons why $G_1$-freeness might force such a decomposition (as for $C_4$-free graphs being a countable union of trees).

Understanding $P1$. $P1$ is a "Folkman-type" property: for each finite $n$, some $G_1$-free graph is edge-Ramsey for $G_2$ under $n$ colours. Try to understand which $(G_1,G_2)$ admit such finite-colour Ramsey obstructions.

I did not obtain a classification. I provide a few rigorous equivalences and structural lemmas relevant to the stated example $(C_4,C_6)$.

WORK

FAST REALITY CHECK (the example $(C_4,C_6)$ for $n=1$)

For $n=1$, property $P1$ for $(C_4,C_6)$ asks for a $C_4$-free graph $H$ such that any 1-colouring (i.e. no colouring choice) contains a monochromatic $C_6$, i.e. simply $H$ contains a $C_6$. Taking $H=C_6$ works and is $C_4$-free. For $n\ge 2$ the existence of such $H$ is nontrivial and is attributed in the problem text to Nešetřil--Rödl.

Lemma 1 (reformulating $P2$ as a decomposition). Fix graphs $G_1,G_2$. For a $G_1$-free graph $H=(V,E)$, the following are equivalent:

1. There exists an edge-colouring $\kappa:E\to\omega$ with no monochromatic copy of $G_2$.
2. The edge-set $E$ can be written as a countable union $E=\bigcup_{n<\omega} E_n$ such that each subgraph $(V,E_n)$ is $G_2$-free.

Proof. $1$$\Rightarrow$$2$: Let $E_n:=\kappa^{-1}(\{n\})$. Then $E=\bigcup_n E_n$. If some $(V,E_n)$ contained a copy of $G_2$, that copy would be monochromatic of colour $n$, contradicting $1$.

$2$$\Rightarrow$$1$: Given $E=\bigcup_n E_n$ with each $(V,E_n)$ $G_2$-free, define a colouring $\kappa$ by $\kappa(e)=\min\{n:e\in E_n\}$. Then for each $n$, the colour class $\kappa^{-1}(\{n\})$ is a subgraph of $(V,E_n)$ and hence is $G_2$-free. Therefore there is no monochromatic copy of $G_2$.$\square$

Lemma 2 (countable union of trees suffices to avoid monochromatic cycles). Let $H=(V,E)$ be a graph. If $E$ is a countable union of edge-sets each of which forms a forest (in particular a tree), then $H$ has an $\aleph_0$-edge-colouring with no monochromatic cycle. In particular, it has an $\aleph_0$-edge-colouring with no monochromatic $C_6$.

Proof. Assume $E=\bigcup_{n<\omega}E_n$ where each $(V,E_n)$ is a forest. Colour every edge $e\in E_n$ with colour $n$ using the "least index" rule to make it a genuine colouring (as in Lemma lem:P2_decomp). For each $n$, the colour class is a subgraph of a forest, hence is a forest, hence contains no cycles of any length. Therefore no cycle (and in particular no $6$-cycle) can be monochromatic.$\square$

Lemma 3 (a basic structural property of $C_4$-free graphs). If a graph $H$ is $C_4$-free, then any two distinct vertices have at most one common neighbour.

Proof. Let $u\neq v$ be vertices. Suppose, for contradiction, that $u$ and $v$ have two distinct common neighbours $x\neq y$. Then the four distinct vertices $u,x,v,y$ form a 4-cycle \[ u-x-v-y-u \] because the edges $ux,xv,vy,yu$ all exist by "common neighbour". This is a copy of $C_4$ in $H$, contradicting that $H$ is $C_4$-free. Therefore $u$ and $v$ have at most one common neighbour.$\square$

VERIFICATION

• Lemma lem:P2_decomp is purely about re-encoding a cover as a colouring (and conversely). It matches the formulation of $P2$.
• Lemma lem:trees_avoid_cycles correctly implies the $C_4,C_6$ example's $P2$ provided we accept the problem-text claim "every $C_4$-free graph is a countable union of trees".
• Lemma lem:C4_codegree checks the standard implication from two common neighbours to a (not-necessarily-induced) 4-cycle.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Property $P2$ for a pair $(G_1,G_2)$ is equivalent to: every $G_1$-free graph is a countable union of $G_2$-free subgraphs (Lemma lem:P2_decomp). In the example $(C_4,C_6)$, the further sufficient condition "countable union of trees" indeed implies $P2$ (Lemma lem:trees_avoid_cycles).

(ii) First gap (crisp). Give a structural characterization of pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. Even for specific natural pairs beyond $(C_4,C_6)$ (e.g. $(K_4,K_3)$, which is Problem 595), no classification is established here.

(iii) Top 3 next moves.

1. Systematically analyze $P2$ as an "arboricity-type" condition: for which $G_1$ does $G_1$-freeness force countable decomposition into $G_2$-free graphs? Try first when $G_2$ is a cycle.
2. For $P1$, attempt to identify which $G_2$ admit $n$-colour edge-Ramsey obstructions inside $G_1$-free graphs (a generalization of Folkman-type existence).
3. Explore whether $P2$ can ever hold when $G_2$ is a clique (e.g. $K_3$) and $G_1$ is also a clique (e.g. $K_4$), by seeking either a decomposition theorem or a transfinite counterexample.

(iv) Minimal counterexample structure. To refute a proposed classification, one would need either: (a) a pair $(G_1,G_2)$ where for every $n$ there exists a $G_1$-free graph $H$ that is edge-Ramsey for $G_2$ under $n$ colours, but some $G_1$-free graph admits no countable decomposition into $G_2$-free subgraphs; or (b) a pair where $P2$ always holds but $P1$ fails for some $n$. For clique pairs like $(K_4,K_3)$, any counterexample must be uncountable and have triangles spread so that every countable edge-colouring traps a monochromatic triangle.

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.

For which graphs $G_1,G_2$ is it true that {UL} {LI} for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet{/LI} {LI} for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$. {/UL} Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees). Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595] .

FORMAL RESTATEMENT

Fix finite graphs $G_1,G_2$. Consider the two properties:

1. $P1$ For every integer $n\ge 1$, there exists a graph $H$ which is $G_1$-free (contains no copy of $G_1$) such that for every edge-colouring $\kappa:E(H)\to[n]$ there exists a monochromatic copy of $G_2$ in $H$.
2. $P2$ For every $G_1$-free graph $H$, there exists an edge-colouring $\kappa:E(H)\to\omega$ such that $H$ has no monochromatic copy of $G_2$.

Problem: classify the pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. The statement notes that $(G_1,G_2)=(C_4,C_6)$ is such a pair.

QUICK LITERATURE/CONTEXT CHECK

I will not import external results beyond what is explicitly stated in the problem text. The text asserts that $(C_4,C_6)$ satisfies $P1$ (due to Nešetřil--Rödl) and $P2$ (due to Erdős--Hajnal), and even notes a strengthening: every $C_4$-free graph is a countable union of trees. The general classification problem is open-ended.

ATTACK PLAN

Understanding $P2$. Rewrite $P2$ as a countable decomposition problem: a countable edge-colouring avoiding monochromatic $G_2$ is the same as writing $E(H)$ as a countable union of $G_2$-free subgraphs. Seek structural reasons why $G_1$-freeness might force such a decomposition (as for $C_4$-free graphs being a countable union of trees).

Understanding $P1$. $P1$ is a "Folkman-type" property: for each finite $n$, some $G_1$-free graph is edge-Ramsey for $G_2$ under $n$ colours. Try to understand which $(G_1,G_2)$ admit such finite-colour Ramsey obstructions.

I did not obtain a classification. I provide a few rigorous equivalences and structural lemmas relevant to the stated example $(C_4,C_6)$.

WORK

FAST REALITY CHECK (the example $(C_4,C_6)$ for $n=1$)

For $n=1$, property $P1$ for $(C_4,C_6)$ asks for a $C_4$-free graph $H$ such that any 1-colouring (i.e. no colouring choice) contains a monochromatic $C_6$, i.e. simply $H$ contains a $C_6$. Taking $H=C_6$ works and is $C_4$-free. For $n\ge 2$ the existence of such $H$ is nontrivial and is attributed in the problem text to Nešetřil--Rödl.

Lemma 1 (reformulating $P2$ as a decomposition). Fix graphs $G_1,G_2$. For a $G_1$-free graph $H=(V,E)$, the following are equivalent:

1. There exists an edge-colouring $\kappa:E\to\omega$ with no monochromatic copy of $G_2$.
2. The edge-set $E$ can be written as a countable union $E=\bigcup_{n<\omega} E_n$ such that each subgraph $(V,E_n)$ is $G_2$-free.

Proof. $1$$\Rightarrow$$2$: Let $E_n:=\kappa^{-1}(\{n\})$. Then $E=\bigcup_n E_n$. If some $(V,E_n)$ contained a copy of $G_2$, that copy would be monochromatic of colour $n$, contradicting $1$.

$2$$\Rightarrow$$1$: Given $E=\bigcup_n E_n$ with each $(V,E_n)$ $G_2$-free, define a colouring $\kappa$ by $\kappa(e)=\min\{n:e\in E_n\}$. Then for each $n$, the colour class $\kappa^{-1}(\{n\})$ is a subgraph of $(V,E_n)$ and hence is $G_2$-free. Therefore there is no monochromatic copy of $G_2$.$\square$

Lemma 2 (countable union of trees suffices to avoid monochromatic cycles). Let $H=(V,E)$ be a graph. If $E$ is a countable union of edge-sets each of which forms a forest (in particular a tree), then $H$ has an $\aleph_0$-edge-colouring with no monochromatic cycle. In particular, it has an $\aleph_0$-edge-colouring with no monochromatic $C_6$.

Proof. Assume $E=\bigcup_{n<\omega}E_n$ where each $(V,E_n)$ is a forest. Colour every edge $e\in E_n$ with colour $n$ using the "least index" rule to make it a genuine colouring (as in Lemma lem:P2_decomp). For each $n$, the colour class is a subgraph of a forest, hence is a forest, hence contains no cycles of any length. Therefore no cycle (and in particular no $6$-cycle) can be monochromatic.$\square$

Lemma 3 (a basic structural property of $C_4$-free graphs). If a graph $H$ is $C_4$-free, then any two distinct vertices have at most one common neighbour.

Proof. Let $u\neq v$ be vertices. Suppose, for contradiction, that $u$ and $v$ have two distinct common neighbours $x\neq y$. Then the four distinct vertices $u,x,v,y$ form a 4-cycle \[ u-x-v-y-u \] because the edges $ux,xv,vy,yu$ all exist by "common neighbour". This is a copy of $C_4$ in $H$, contradicting that $H$ is $C_4$-free. Therefore $u$ and $v$ have at most one common neighbour.$\square$

VERIFICATION

• Lemma lem:P2_decomp is purely about re-encoding a cover as a colouring (and conversely). It matches the formulation of $P2$.
• Lemma lem:trees_avoid_cycles correctly implies the $C_4,C_6$ example's $P2$ provided we accept the problem-text claim "every $C_4$-free graph is a countable union of trees".
• Lemma lem:C4_codegree checks the standard implication from two common neighbours to a (not-necessarily-induced) 4-cycle.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Property $P2$ for a pair $(G_1,G_2)$ is equivalent to: every $G_1$-free graph is a countable union of $G_2$-free subgraphs (Lemma lem:P2_decomp). In the example $(C_4,C_6)$, the further sufficient condition "countable union of trees" indeed implies $P2$ (Lemma lem:trees_avoid_cycles).

(ii) First gap (crisp). Give a structural characterization of pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. Even for specific natural pairs beyond $(C_4,C_6)$ (e.g. $(K_4,K_3)$, which is Problem 595), no classification is established here.

(iii) Top 3 next moves.

1. Systematically analyze $P2$ as an "arboricity-type" condition: for which $G_1$ does $G_1$-freeness force countable decomposition into $G_2$-free graphs? Try first when $G_2$ is a cycle.
2. For $P1$, attempt to identify which $G_2$ admit $n$-colour edge-Ramsey obstructions inside $G_1$-free graphs (a generalization of Folkman-type existence).
3. Explore whether $P2$ can ever hold when $G_2$ is a clique (e.g. $K_3$) and $G_1$ is also a clique (e.g. $K_4$), by seeking either a decomposition theorem or a transfinite counterexample.

(iv) Minimal counterexample structure. To refute a proposed classification, one would need either: (a) a pair $(G_1,G_2)$ where for every $n$ there exists a $G_1$-free graph $H$ that is edge-Ramsey for $G_2$ under $n$ colours, but some $G_1$-free graph admits no countable decomposition into $G_2$-free subgraphs; or (b) a pair where $P2$ always holds but $P1$ fails for some $n$. For clique pairs like $(K_4,K_3)$, any counterexample must be uncountable and have triangles spread so that every countable edge-colouring traps a monochromatic triangle.