Erdős Problem #570

Erdős Problem 570

Statement and scope.

A construction showing that the proposed bound is sharp.

Matching upper bound via the stated matching theorem.

Consider any colouring of $K_N$, with $N=2m+t$ and $m\geq k$. If its blue graph has no matching of size $m$, the formula gives \[ o(G-S)\geq t+2+|S|. \] Since $o(G-S)\leq N-|S|$, this also implies $|S|\leq m-1$. Hence $G-S$ has at least $m+t+1\geq k$ vertices and at least $t+2$ components. Edges joining distinct blue components are red.

If there are at least $k$ components, choose one vertex from each of $k$ of them to obtain a red clique. Otherwise, choose $k$ vertices meeting every component, first choosing one from each and then adding arbitrary available vertices. The complete multipartite red subgraph on these vertices has no part of size larger than \[ k-(t+2)+1=k-t-1=\lfloor k/2\rfloor. \] Its minimum degree is therefore at least $\lceil k/2\rceil$. It has a Hamilton cycle by the elementary argument below. This gives a red $C_k$ and proves, together with $2$, \[ R(C_k,mK_2)=2m+\left\lfloor\frac{k-1}{2}\right\rfloor \qquad(m\geq k). \tag{3} \]

The Hamilton-cycle step, proved explicitly.

Another full case: a triangle versus a tree.

It follows that a graph containing no $T$ is $(m-1)$-degenerate: every nonempty subgraph must have a vertex of degree at most $m-1$. Repeated deletion and reverse greedy colouring make it $m$-colourable. If a blue graph on $2m+1$ vertices has no $T$, one of these independent colour classes has at least three vertices, giving a red triangle. This proves the upper bound in $4$. For the lower bound, take two blue cliques of size $m$, with all cross edges red. Blue has no connected graph on $m+1$ vertices, and the red bipartite graph has no triangle. Since a tree has $m$ edges, $4$ is exactly $1$ for this case.

Remaining gap and attribution.

The matching proof is reconstructed from Proposition 9 of Cambie, Freschi, Morawski, Petrova and Pokrovskiy, Ramsey number of a cycle versus a graph of a given size, https://arxiv.org/abs/2601.10238. Their Theorem 3 settles the previously missing odd $k\geq7$ cases for arbitrary targets, with earlier results covering the other cycle lengths. That general induction is not proved here. The Tutte--Berge formula is the only external input used in $3$; the other displayed constructions and the tree case are proved in full. Current statement: https://www.erdosproblems.com/570, checked 24 September 2026. No novelty is claimed.

Completion estimate.

1) FORMAL RESTATEMENT

For $k\ge 3$, the problem asks whether the following inequality holds:

For every graph $H$ with $m=e(H)$ edges and with no isolated vertices, \[ R(C_k,H) \le 2m+\left\lceil\frac{k-1}{2}\right\rceil. \]

2) QUICK LITERATURE/CONTEXT CHECK

The problem file notes that this statement was proved for even $k$ by Erdős, Faudree, Rousseau, and Schelp [EFRS93], and for $k=3$ by Sidorenko [Si93].

3) ATTACK PLAN

Before attempting a proof, check for small-$m$ obstructions. In particular, test $m=1$ (so $H=K_2$) because $R(C_k,K_2)$ is elementary.

4) WORK

Fast reality check.

Take $m=1$, so $H=K_2$. Then $R(C_k,K_2)=k$ (Lemma 570.1 below). For $k\ge 5$ the proposed upper bound evaluates to \[ 2\cdot 1+\left\lceil\frac{k-1}{2}\right\rceil = 2+\left\lceil\frac{k-1}{2}\right\rceil < k, \] so the inequality fails.

Lemma 570.1 (exact value for $H=K_2$). For every $k\ge 3$, \[ R(C_k,K_2)=k. \]

Proof. This is exactly Lemma 569.1 specialised to $\ell=k$. (The proof is repeated briefly.)

- In $K_{k-1}$ colour all edges red. Then there is no blue edge and no red $C_k$ (not enough vertices), so $R(C_k,K_2)>k-1$.

- In $K_k$, any colouring either has a blue edge (giving blue $K_2$) or is all red, in which case the red $K_k$ contains a $C_k$.

Hence $R(C_k,K_2)=k$. $\square$

Lemma 570.2 (the proposed inequality fails for all $k\ge 5$). For every $k\ge 5$, \[ R(C_k,K_2)=k > 2+\left\lceil\frac{k-1}{2}\right\rceil. \]

Proof. By Lemma 570.1, $R(C_k,K_2)=k$.

For $k\ge 5$ we have $\lceil (k-1)/2\rceil \le k/2$ (since $\lceil x\rceil\le x+1/2$ for half-integers, and here $(k-1)/2$ is either an integer or a half-integer). Thus \[ 2+\left\lceil\frac{k-1}{2}\right\rceil \le 2+\frac{k}{2}. \] Now $k>2+k/2$ is equivalent to $k/2>2$, i.e. $k>4$, which holds for all $k\ge 5$. Therefore \[ 2+\left\lceil\frac{k-1}{2}\right\rceil < k = R(C_k,K_2). \] So the claimed inequality fails when $H=K_2$ (which has $m=1$ and no isolated vertices). $\square$

Additional computed checks for $k=5$ and matchings. Although the conjectured inequality is false as stated, for $k=5$ and $m\ge 2$ it matches small computed values for matchings: \[ R(C_5,2K_2)=6 = 2\cdot 2+2,\qquad R(C_5,3K_2)=8=2\cdot 3+2. \]

5) VERIFICATION

- The counterexample uses $H=K_2$ (one edge, no isolated vertices) and the exact evaluation $R(C_k,K_2)=k$.

- The strict inequality $2+\lceil (k-1)/2\rceil<k$ is checked explicitly in Lemma 570.2.

- The numerical checks $R(C_5,2K_2)=6$ and $R(C_5,3K_2)=8$ were computed locally by exhaustive search/backtracking.

6) FINAL

LABEL: FULL SOLUTION

SUBLABEL: COUNTEREXAMPLE/DISPROOF

The statement "for all $k\ge 3$ and all $m$-edge graphs $H$ without isolated vertices, $R(C_k,H)\le 2m+\lceil (k-1)/2\rceil$" is false.

A concrete counterexample is: take any $k\ge 5$ and take $H=K_2$ (so $m=1$). Then $R(C_k,K_2)=k$ (Lemma 570.1), but the proposed bound gives $2+\lceil (k-1)/2\rceil<k$ (Lemma 570.2), contradicting the inequality.

(If one wants a corrected version consistent with standard conventions, a minimal repair is to add a hypothesis "$m$ is sufficiently large (depending on $k$)", or to replace the right-hand side by $\max\{k,\,2m+\lceil (k-1)/2\rceil\}$. The corrected statement is not proved here.)