Erdős Problem #545

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

REUSED SOURCE 1

A question of Erdős and Graham. Suppose $G$ is a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is as complete as possible? More precisely, if $m=\tbinom{n}{2}+t$ with $0\leq t<n$, is it true that $R(G)\leq R(H)$, where $H$ is the graph formed by connecting a new vertex to $t$ vertices of $K_n$?

1) “FORMAL RESTATEMENT”

Let $m\ge 1$ be an integer. Let $\mathcal{G}_m$ be the family of finite simple graphs with exactly $m$ edges and no isolated vertices. For $m=\binom{n}{2}+t$ with $n$ maximal and $0\le t < n$, define $H_m$ to be the graph obtained from $K_n$ by adding one new vertex joined to exactly $t$ vertices of the $K_n$ (note: when $t=0$, this construction produces an isolated vertex; since the quantification restricts to graphs with no isolated vertices, the natural comparison graph is $K_n$ itself, but in the counterexample below $t\neq 0$ so no ambiguity arises).

Conjecture (as stated): For every $G\in\mathcal{G}_m$, \[ R(G)\le R(H_m), \] where $R(\cdot)$ denotes the ordinary (two-colour) Ramsey number of a graph.

I will disprove this conjecture by exhibiting $m=2$ and a graph $G\in\mathcal{G}_2$ with $R(G)>R(H_2)$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement notes (i) a weaker upper bound question $R(G)\le 2^{O(m^{1/2})}$ is true (Sudakov), and (ii) LouisD observed the conjectured extremiser fails for small $m$ (in particular $2\le m\le 5$ and $7\le m\le 9$). I will give an explicit self-contained counterexample at $m=2$.

3) “ATTACK PLAN”

For $m=2$, compute the proposed extremal graph $H_2$ and its Ramsey number. Then find another $2$-edge graph $G$ with no isolated vertices whose Ramsey number is larger. To make the disproof fully self-contained, prove the exact Ramsey numbers needed.

4) “WORK”

For $m=2$ we have $2=\binom{2}{2}+1$, so $n=2$ and $t=1$. Thus $H_2$ is obtained from $K_2$ by adding one new vertex adjacent to exactly one endpoint of the $K_2$. This is exactly the path $P_3$ on three vertices.

Let $G$ be the disjoint union of two edges, i.e. the matching $2K_2$ on $4$ vertices. Note $G$ has $m=2$ edges and no isolated vertices.

I now compute $R(P_3)$ and $R(2K_2)$.

Lemma 1 (Exact value $R(P_3)=3$).

Proof. A copy of $P_3$ consists of two adjacent edges on three vertices.

- Lower bound: $R(P_3)\ge 3$ because $K_2$ has only one edge and cannot contain $P_3$ in either colour.

- Upper bound: In any red/blue colouring of the edges of $K_3$, there are three edges. By the pigeonhole principle, at least two edges have the same colour. In a triangle, any two distinct edges share a vertex, hence these two same-coloured edges form a monochromatic copy of $P_3$.

Therefore $R(P_3)=3$. $\square$

Lemma 2 (Exact value $R(2K_2)=5$).

Proof. A monochromatic copy of $2K_2$ is a monochromatic matching of size $2$.

Step 1: $R(2K_2)\ge 5$. Consider $K_4$ on vertices $\{0,1,2,3\}$. Colour the three edges among $\{1,2,3\}$ red, and colour the three edges incident to $0$ blue. Then: - The red edges form a triangle, so any two red edges share a vertex (no red matching of size $2$). - The blue edges form a star centred at $0$, so any two blue edges share the vertex $0$ (no blue matching of size $2$). Hence this colouring of $K_4$ contains no monochromatic $2K_2$, and therefore $R(2K_2)\ge 5$.

Step 2: $R(2K_2)\le 5$. Assume for contradiction that there is a red/blue colouring of $K_5$ with no monochromatic matching of size $2$. Then: - The set of red edges is pairwise intersecting (any two red edges share a vertex), otherwise two disjoint red edges would form a red $2K_2$. - Similarly, the set of blue edges is pairwise intersecting.

Claim: In $K_5$, any pairwise-intersecting set of edges has size at most $4$.

Proof of claim. Take any edge $ab$ in the set. Every other edge in the set must intersect $ab$, so every other edge must be incident to $a$ or to $b$. If there is an edge $ac$ with $c\notin\{a,b\}$ and an edge $bd$ with $d\notin\{a,b\}$ and $c\neq d$, then $ac$ and $bd$ are disjoint, contradicting pairwise intersection. Therefore all edges in the set must share a common vertex (either $a$ or $b$), i.e. the set is contained in a star, which has exactly $4$ edges in $K_5$. This proves the claim. $\square$

Applying the claim to both colours, we get \[ |E_{\text{red}}|\le 4 \quad\text{and}\quad |E_{\text{blue}}|\le 4, \] so $|E(K_5)|=|E_{\text{red}}|+|E_{\text{blue}}|\le 8$, contradicting $|E(K_5)|=10$. Thus every colouring of $K_5$ contains a monochromatic $2K_2$, and hence $R(2K_2)\le 5$.

Combining Step 1 and Step 2 gives $R(2K_2)=5$. $\square$

Disproof. For $m=2$ the conjectured extremiser is $H_2=P_3$ with $R(H_2)=3$ (Lemma 1). The graph $G=2K_2$ has $R(G)=5$ (Lemma 2). Hence $R(G)>R(H_2)$, contradicting the conjecture.

5) “VERIFICATION”

Fast reality check by exhaustive search: - Brute force over all $2^{\binom{3}{2}}=8$ colourings of $K_3$ confirms $R(P_3)=3$. - Brute force over all $2^{\binom{4}{2}}=64$ colourings of $K_4$ finds a colouring avoiding monochromatic $2K_2$ (the star/triangle construction above). - Brute force over all $2^{\binom{5}{2}}=1024$ colourings of $K_5$ finds none avoiding monochromatic $2K_2$.

6) FINAL

COUNTEREXAMPLE/DISPROOF

Counterexample at $m=2$: $G=2K_2$ beats the proposed extremiser $H_2=P_3$.

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.

A question of Erdős and Graham. Suppose $G$ is a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is as complete as possible? More precisely, if $m=\tbinom{n}{2}+t$ with $0\leq t<n$, is it true that $R(G)\leq R(H)$, where $H$ is the graph formed by connecting a new vertex to $t$ vertices of $K_n$?

1) “FORMAL RESTATEMENT”

Let $m\ge 1$ be an integer. Let $\mathcal{G}_m$ be the family of finite simple graphs with exactly $m$ edges and no isolated vertices. For $m=\binom{n}{2}+t$ with $n$ maximal and $0\le t < n$, define $H_m$ to be the graph obtained from $K_n$ by adding one new vertex joined to exactly $t$ vertices of the $K_n$ (note: when $t=0$, this construction produces an isolated vertex; since the quantification restricts to graphs with no isolated vertices, the natural comparison graph is $K_n$ itself, but in the counterexample below $t\neq 0$ so no ambiguity arises).

Conjecture (as stated): For every $G\in\mathcal{G}_m$, \[ R(G)\le R(H_m), \] where $R(\cdot)$ denotes the ordinary (two-colour) Ramsey number of a graph.

I will disprove this conjecture by exhibiting $m=2$ and a graph $G\in\mathcal{G}_2$ with $R(G)>R(H_2)$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem statement notes (i) a weaker upper bound question $R(G)\le 2^{O(m^{1/2})}$ is true (Sudakov), and (ii) LouisD observed the conjectured extremiser fails for small $m$ (in particular $2\le m\le 5$ and $7\le m\le 9$). I will give an explicit self-contained counterexample at $m=2$.

3) “ATTACK PLAN”

For $m=2$, compute the proposed extremal graph $H_2$ and its Ramsey number. Then find another $2$-edge graph $G$ with no isolated vertices whose Ramsey number is larger. To make the disproof fully self-contained, prove the exact Ramsey numbers needed.

4) “WORK”

For $m=2$ we have $2=\binom{2}{2}+1$, so $n=2$ and $t=1$. Thus $H_2$ is obtained from $K_2$ by adding one new vertex adjacent to exactly one endpoint of the $K_2$. This is exactly the path $P_3$ on three vertices.

Let $G$ be the disjoint union of two edges, i.e. the matching $2K_2$ on $4$ vertices. Note $G$ has $m=2$ edges and no isolated vertices.

I now compute $R(P_3)$ and $R(2K_2)$.

Lemma 1 (Exact value $R(P_3)=3$).

Proof. A copy of $P_3$ consists of two adjacent edges on three vertices.

- Lower bound: $R(P_3)\ge 3$ because $K_2$ has only one edge and cannot contain $P_3$ in either colour.

- Upper bound: In any red/blue colouring of the edges of $K_3$, there are three edges. By the pigeonhole principle, at least two edges have the same colour. In a triangle, any two distinct edges share a vertex, hence these two same-coloured edges form a monochromatic copy of $P_3$.

Therefore $R(P_3)=3$. $\square$

Lemma 2 (Exact value $R(2K_2)=5$).

Proof. A monochromatic copy of $2K_2$ is a monochromatic matching of size $2$.

Step 1: $R(2K_2)\ge 5$. Consider $K_4$ on vertices $\{0,1,2,3\}$. Colour the three edges among $\{1,2,3\}$ red, and colour the three edges incident to $0$ blue. Then: - The red edges form a triangle, so any two red edges share a vertex (no red matching of size $2$). - The blue edges form a star centred at $0$, so any two blue edges share the vertex $0$ (no blue matching of size $2$). Hence this colouring of $K_4$ contains no monochromatic $2K_2$, and therefore $R(2K_2)\ge 5$.

Step 2: $R(2K_2)\le 5$. Assume for contradiction that there is a red/blue colouring of $K_5$ with no monochromatic matching of size $2$. Then: - The set of red edges is pairwise intersecting (any two red edges share a vertex), otherwise two disjoint red edges would form a red $2K_2$. - Similarly, the set of blue edges is pairwise intersecting.

Claim: In $K_5$, any pairwise-intersecting set of edges has size at most $4$.

Proof of claim. Take any edge $ab$ in the set. Every other edge in the set must intersect $ab$, so every other edge must be incident to $a$ or to $b$. If there is an edge $ac$ with $c\notin\{a,b\}$ and an edge $bd$ with $d\notin\{a,b\}$ and $c\neq d$, then $ac$ and $bd$ are disjoint, contradicting pairwise intersection. Therefore all edges in the set must share a common vertex (either $a$ or $b$), i.e. the set is contained in a star, which has exactly $4$ edges in $K_5$. This proves the claim. $\square$

Applying the claim to both colours, we get \[ |E_{\text{red}}|\le 4 \quad\text{and}\quad |E_{\text{blue}}|\le 4, \] so $|E(K_5)|=|E_{\text{red}}|+|E_{\text{blue}}|\le 8$, contradicting $|E(K_5)|=10$. Thus every colouring of $K_5$ contains a monochromatic $2K_2$, and hence $R(2K_2)\le 5$.

Combining Step 1 and Step 2 gives $R(2K_2)=5$. $\square$

Disproof. For $m=2$ the conjectured extremiser is $H_2=P_3$ with $R(H_2)=3$ (Lemma 1). The graph $G=2K_2$ has $R(G)=5$ (Lemma 2). Hence $R(G)>R(H_2)$, contradicting the conjecture.

5) “VERIFICATION”

Fast reality check by exhaustive search: - Brute force over all $2^{\binom{3}{2}}=8$ colourings of $K_3$ confirms $R(P_3)=3$. - Brute force over all $2^{\binom{4}{2}}=64$ colourings of $K_4$ finds a colouring avoiding monochromatic $2K_2$ (the star/triangle construction above). - Brute force over all $2^{\binom{5}{2}}=1024$ colourings of $K_5$ finds none avoiding monochromatic $2K_2$.

6) FINAL

COUNTEREXAMPLE/DISPROOF

Counterexample at $m=2$: $G=2K_2$ beats the proposed extremiser $H_2=P_3$.