Erdős problem 596 — wave 6e

Date: 2026-07-27 (UTC)

0. Mandatory live-page gate

I fetched the live page through the Bright Data browser path, not through

datacenter curl (which was independently confirmed to receive a Cloudflare

403). I also opened the discussion thread and clicked the bibliography entry

on the live page.

Live page: <https://www.erdosproblems.com/596>

Verbatim current statement

> For which graphs \(G_1,G_2\) is it true that

>

> - 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

> - for every graph \(H\) without a \(G_1\) there is an \(\aleph_0\)-colouring of the edges of \(H\) without a monochromatic \(G_2\).

The live page says:

• status: OPEN;
• claimed proofs: 0;
• interested in collaborating: None;
• currently working on this problem: None;
• formalised statement: Yes;
• one comment.

The one comment is by sammausberg, timestamped 17:59 on 29 April 2026.

It asks whether an uncountably chromatic copy hypergraph can be thinned or

extended to a canonical, order-pattern-controlled obstruction, motivated by

\((G_1,G_2)=(K_4,K_3)\). It is a question, not a result or proof claim; the

site itself marks comments as unverified.

The page's listed known results are:

1. Erdős and Hajnal originally conjectured that there are no such pairs.

2. \((C_4,C_6)\) is an example: Nešetřil and Rödl give the finite-colour

property, while Erdős and Hajnal give the countable-colour escape; indeed,

every \(C_4\)-free graph is a countable union of trees.

3. The case \((K_4,K_3)\) is Problem 595.

Clicking [Er87] on the live page gives the exact reference:

> P. Erdős, Some problems on finite and infinite graphs, in *Logic and

> Combinatorics* (Arcata, Calif., 1985), Contemporary Mathematics 65 (1987),

> 223–228. MR 891250.

There is therefore no skip condition, and the run proceeded.

1. Scope and claim labels

I treat graphs as simple, copies as ordinary (not necessarily induced)

subgraphs, and \(P_4\) as the path with four vertices and three edges. The

result below classifies the complete \(G_1=C_4\) slice for every finite target

graph \(F\). Isolated vertices cause no change; details are included in the

proof.

Claim labels required by the task:

• (a) elementary-rigorous: proved below without an external theorem;
• (b) rigorous-modulo-named-theorem: deduction is proved, with the named

theorem and primary source identified;

• (c) plausible/structural-unverified: not used for any conclusion;
• (d) computational-only: exhaustively checked by the companion program.

2. Primary-source literature check

Erdős–Hajnal decomposition

Erdős and Hajnal, On decomposition of graphs, Acta Math. Acad. Sci. Hungar.

18 (1967), 359–377, DOI

10.1007/BF02280296, is available from

the Rényi Institute archive.

Their Theorem 10 says that a graph containing no quadrilateral has an

edge-decomposition of type \(\omega\) whose members are “trees”; immediately

before the theorem they define a tree to mean a graph with no circuits. Thus

“tree” there permits a disconnected forest. This directly verifies the

infinite decomposition used on the problem page. (b)

Original formulation

The Rényi scan of Er87, Problem 5

on pp. 224–225, states the finite-versus-infinite-colour question. It also

records the \(C_4\)-free decomposition and says that the Nešetřil–Rödl result

works for a bipartite target not containing \(C_4\), not merely for the

displayed cycle example. OCR of the cycle subscript is poor, so I use the

live page—not OCR—to identify the displayed example as \(C_6\).

The finite Ramsey input that closes the \(C_4\) slice

Nešetřil and Rödl, On Ramsey graphs without bipartite subgraphs, Discrete

Mathematics 101 (1992), 223–229, DOI

10.1016/0012-365X(92)90605-F90605-F),

states in the publisher's abstract that every graph \(F\) containing neither

a triangle nor the specified \(K_{m,n}\) has a Ramsey graph with the same two

exclusions. It also says that the paper characterises the edge-Ramsey classes

\(\operatorname{Forb}(K_{m,n})\). Its \(m=n=2\) case is precisely the fact

needed here: every triangle-free, \(C_4\)-free finite graph \(F\) has a

triangle-free, \(C_4\)-free red/blue Ramsey graph. (b)

A two-colour statement is enough for every finite number of colours: iterate

the theorem and successively split an \(r\)-colour palette according to the

bits of its colour labels. This iteration is written out below. (a)

Exact-phrase and citation searches found no primary source explicitly

formulating the complete classification of the \(G_1=C_4\) row below, and no

source settling the full all-\(G_1\) Problem 596. This is only an honest

search report, not a claim that no such paper exists.

3. Exact classification when \(G_1=C_4\)

Theorem

For every finite simple graph \(F\),

The equivalence is (b) overall: all reductions and necessity arguments are

elementary, while sufficiency uses the two named theorems above.

3.1. Two elementary structural facts

Fact 1. A triangle-free graph containing no \(P_4\) is a star forest.

Conversely, a star forest is triangle-free and contains no \(P_4\). (a)

Proof. If an edge \(uv\) has \(\deg u,\deg v\geq2\), choose

\(x\in N(u)\setminus\{v\}\) and \(y\in N(v)\setminus\{u\}\).

Triangle-freeness gives \(x\ne y\), so \(xuvy\) is a (not necessarily induced)

\(P_4\). Therefore, in a \(P_4\)-free triangle-free graph, no two vertices of

degree at least two are adjacent. Every nontrivial connected component is

then a star. The converse is immediate.

Fact 2. Every \(C_4\)-free graph is the union of countably many star

forests. (b)

Proof. Erdős–Hajnal decompose its edges into countably many forests. In each

tree component choose a root. Colour an edge by the distance from the root

of its shallower endpoint. For a fixed distance \(j\), all such edges form

vertex-disjoint stars centred at level \(j\). Thus each forest is a

countable union of star forests, and

\(\aleph_0\cdot\aleph_0=\aleph_0\).

3.2. Necessity in (1)

Assume \((C_4,F)\) has both properties.

1. \(F\) cannot contain \(C_4\). The \(n=1\) finite-colour property

requires a \(C_4\)-free graph containing \(F\), impossible if

\(C_4\subseteq F\). (a)

2. \(F\) cannot contain a triangle. In a \(C_4\)-free graph, no edge is

contained in two distinct triangles: two triangles sharing \(uv\), with

third vertices \(x\ne y\), create the four-cycle \(xuyvx\). Hence all

triangles have pairwise disjoint edge sets. In every triangle colour one

edge red and the other two blue; colour all unused edges arbitrarily.

This is a consistent red/blue colouring with no monochromatic triangle,

and therefore no monochromatic copy of any \(F\) containing a triangle.

The finite-colour property fails at \(n=2\). (a)

3. \(F\) must contain \(P_4\). We now know that \(F\) is triangle-free.

If it contains no \(P_4\), Fact 1 makes it a finite star forest. Let its

nontrivial components be \(K_{1,d_1},\ldots,K_{1,d_s}\). Form a forest

\(X\) consisting of \(\aleph_1\) disjoint copies of

\(K_{1,\aleph_1}\). In any countable edge-colouring, at every centre some

colour occurs on uncountably many incident edges. Among the

\(\aleph_1\) centres, uncountably many choose the same such colour.

Select \(s\) of those centres and respectively \(d_1,\ldots,d_s\) leaves.

This is a monochromatic \(F\) (and there are ample unused vertices for any

isolated vertices of \(F\)). Thus this \(C_4\)-free \(X\) has no

countable \(F\)-avoiding edge-colouring, contradicting the second

property. (a)

For an edgeless \(F\), its empty edge set is vacuously monochromatic in every

host with enough vertices, so the second property fails as well. (a)

3.3. Sufficiency in (1)

Assume that \(F\) is triangle-free, \(C_4\)-free, and contains \(P_4\).

Finite-colour property. Put \(F_0=F\). Applying the

Nešetřil–Rödl 1992 theorem with \(m=n=2\), recursively choose a finite

triangle-free, \(C_4\)-free graph \(F_{i+1}\) such that

For \(r\) colours choose \(k\) with \(r\leq2^k\) and label the colours by

distinct \(k\)-bit strings. In \(F_k\), group edge colours by their first

bit and find a monochromatic-bit copy of \(F_{k-1}\); inside that copy group

by the second bit, and continue. The final copy of \(F_0\) has one complete

bit string, hence one original colour. Every \(F_k\) is \(C_4\)-free.

This proves the first property for every finite \(r\). (b)

If \(F\) has isolated vertices, apply the construction to the graph obtained

by deleting them and add sufficiently many isolated vertices to each host.

Ordinary subgraph copies then recover \(F\). (a)

Countable-colour property. By Fact 2, every \(C_4\)-free graph \(H\)

has an edge-colouring with countably many colours in which every colour class

is a star forest. No star forest contains \(P_4\), while every copy of \(F\)

does. Hence this colouring has no monochromatic \(F\). (b)

This completes the proof of (1).

Consequences

• The page's \((C_4,C_6)\) example is one member of an exact row, not an

isolated case.

• Every \(C_\ell\) with \(\ell\geq5\) qualifies.
• More unexpectedly, every non-star tree qualifies. In particular,

\((C_4,P_4)\) has the two properties. (b)

4. An explicit sharp small case: \(F=P_4\)

The companion computation found the following graph \(W\) on vertices

\(\{0,\ldots,8\}\):

Equivalently, take the two 5-cycles

which share the path \(6,2,7\); add the edge \(08\), making the triangle

\((0,6,8)\); and add the pendant edges \(38\) and \(15\).

Its graph6 string is `H?DBRQ`` (the third character is a backtick).

The from-scratch check gives: (d)

• \(W\) is \(C_4\)-free (every pair of vertices has at most one common

neighbour);

• \(W\) has 31 distinct three-edge sets supporting a \(P_4\);
• all \(2^{11}=2048\) red/blue edge-colourings were enumerated;
• every colouring has a monochromatic \(P_4\);
• the minimum number of monochromatic \(P_4\) edge-sets is exactly 1, attained

by 22 colourings.

Thus (2) is an explicit two-colour finite witness for the new smallest target

in the classified row.

Exact minimum order

Using nauty 2.8.8 geng -cq n, the verifier generated every connected

unlabelled graph through \(n=9\). It parsed graph6 itself, tested \(C_4\)

by common-neighbour counts, generated all \(P_4\) edge triples, and solved

the red/blue avoidance question by direct colouring enumeration. A

disconnected graph arrows a connected target \(P_4\) only if one component

does, so connected generation is sufficient. (d)

| \(n\) | connected unlabelled | \(C_4\)-free | \(C_4\)-free \(W\to(P_4)^e_2\) |

|---:|---:|---:|---:|

| 1 | 1 | 1 | 0 |

| 2 | 1 | 1 | 0 |

| 3 | 2 | 2 | 0 |

| 4 | 6 | 3 | 0 |

| 5 | 21 | 8 | 0 |

| 6 | 112 | 19 | 0 |

| 7 | 853 | 57 | 0 |

| 8 | 11117 | 186 | 0 |

| 9 | 261080 | 740 | 10 |

Consequently, the minimum order of a \(C_4\)-free red/blue Ramsey graph for

\(P_4\) is exactly \(9\). There are 10 such isomorphism classes at order 9,

and their minimum edge count is 11, achieved by (2). (d)

Exact small-target table

Combining (1) with the isomorphism-complete generation gives the number of

connected qualifying targets \(F\) on \(v\leq6\) vertices: (b)+(d)

| \(v(F)\) | number | targets |

|---:|---:|---|

| 1,2,3 | 0 | none |

| 4 | 1 | \(P_4\) |

| 5 | 3 | \(P_5\); \(K_{1,3}\) with one edge subdivided; \(C_5\) |

| 6 | 7 | the five non-star trees; \(C_5\) with one pendant leaf; \(C_6\) |

The classification (1), rather than this finite table, handles all finite

targets and also disconnected ones.

5. Reproduction

Standalone verifier:

Command:

python runs/erdos596_wave6e_verify.py

Observed salient output:

Explicit witness:
  graph6='H?`DBRQ', vertices=9, edges=11, P4 edge-sets=31
  C4-free: yes
  checked colourings: 2048
  minimum monochromatic P4 edge-sets: 1 (attained by 22 colourings)
...
  conclusion: the minimum C4-free red/blue Ramsey order for P4 is 9
  at n=9: 10 isomorphism classes; minimum edge count 11

ALL CHECKS PASSED

Wall time on this VM was 9.54 seconds. The script uses only the Python

standard library; nauty is invoked solely for the complete unlabelled census.

--witness-only checks (2) over all 2048 colourings without nauty.

SHA-256 at the time of this report:

5ed2bcb153b83f16b2f3a9abf66075f610548abb5e93352935c74b0f7db751bc

The essential witness check implemented in the standalone file is:

WITNESS_EDGES = (
    (0, 4), (0, 6), (0, 8), (1, 5), (1, 7), (1, 8),
    (2, 6), (2, 7), (3, 8), (4, 7), (6, 8),
)

# A C4 exists iff a pair of vertices has two common neighbours.
assert all((adj[u] & adj[v]).bit_count() < 2
           for u in range(9) for v in range(u + 1, 9))

# p4_edge_sets() lists the three edge indices of every non-induced P4.
copies = p4_edge_sets(9, WITNESS_EDGES)
for colouring in range(1 << len(WITNESS_EDGES)):
    assert any(
        ((colouring >> i) & 1)
        == ((colouring >> j) & 1)
        == ((colouring >> k) & 1)
        for i, j, k in copies
    )

The full file additionally contains its own graph6 decoder, structural audits,

complete census, expected-count assertions, and sharp histogram.

6. What remains and the precise wall

This does not characterise pairs with arbitrary \(G_1\), so it does not

close Problem 596.

For a graph \(H\), let \(X_F(H)\) be the hypergraph whose vertices are

\(E(H)\) and whose hyperedges are the edge-sets of copies of \(F\). The full

problem asks when

is unbounded over the finite cardinals while every individual value is at

most \(\aleph_0\). The \(C_4\) row works because two unusually well-matched

theorems are available:

1. Nešetřil–Rödl preserve triangle- and \(C_4\)-freeness under the finite

Ramsey construction.

2. Erdős–Hajnal give countable forest decomposition, which the elementary

depth argument sharpens to countable star-forest decomposition.

For general \(G_1\), the missing ingredient is an analogue that identifies

the smallest hereditary class into which every \(G_1\)-free graph can be

countably edge-decomposed, together with a finite Ramsey theorem that

preserves \(G_1\)-freeness for precisely the complementary targets. Even the

specific \((K_4,K_3)\) countable-decomposition question is exactly the still

open Problem 595, as the live page notes. Finite enumeration cannot decide

that arbitrary-cardinal statement. This is the exact uniformity/infinite

step that prevents promoting the present row classification to a solution of

Problem 596.

No claim in this report is category (c).

PARTIAL: Classified every finite target in the full \(G_1=C_4\) row—exactly the triangle-free, \(C_4\)-free graphs containing \(P_4\)—and found/verified the minimum 9-vertex, 11-edge \(C_4\)-free red-blue Ramsey witness for \(P_4\); the all-\(G_1\) problem remains open.