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.

1. 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)

1. \(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)

1. \(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)

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)

The classification (1), rather than this finite table, handles all finite targets and also disconnected ones.

5. Reproduction

Standalone verifier:

runs/erdos596_wave6e_verify.py

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.

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