Erdős Problem #85

Erdős Problem 85: minimum degree and four-cycle-free extensions

1. Statement and scope

2. Universal comparisons and the degree bound

In a $C_4$-free graph, two distinct vertices have at most one common neighbor. Counting unordered pairs of neighbors by their middle vertex gives \[ \sum_v\binom{\deg(v)}2\le\binom n2. \] Thus $d(n)(d(n)-1)\le n-1$, and \[ f(n)\le1+\left\lfloor\frac{1+\sqrt{4n-3}}2\right\rfloor.\tag{3} \] Triangles are allowed throughout; no triangle-free assumption has slipped into this count.

3. The exact extension condition

Indeed, every new four-cycle must contain $x$, and has the form $x-u-w-v-x$, where $u,v\in S$ share the old neighbor $w$. Conversely any such common neighbor produces this cycle; all four vertices are distinct because $G$ is simple. No other kind of new four-cycle is possible. In particular, if $\delta(G)\ge d$ and $\alpha(J)\ge d$, choose $S$ of size $d$. The new vertex has degree $d$, all old degrees do not decrease, and this gives an $(n+1)$-vertex example of minimum degree at least $d$.

If $G$ has maximum degree $\Delta$, each vertex has at most $\Delta(\Delta-1)$ neighbors in $J$, by counting two-step walks with a different endpoint. Greedily choosing a vertex and deleting it and its neighbors in $J$ produces an independent set of size at least \[ \frac{n}{1+\Delta(\Delta-1)}. \] Hence the sufficient quantitative condition \[ n\ge d\left(1+\Delta(\Delta-1)\right)\tag{4} \] proves that this particular $G$ can be extended while preserving minimum degree $d$.

Condition $4$ is inadequate near the extremal scale $d\asymp\sqrt n$: even when $\Delta\asymp d$, its right side has order $d^3$. The exact independent-set criterion may hold without $4$, but there is no proof that every extremal graph has the required independent set in $J$. Also, failure to extend a particular extremal graph would not disprove monotonicity: a different graph on $n+1$ vertices might work.

4. An explicit nontrivial example

5. Assessment and attribution

Completion rate estimate: 25%.

FORMAL RESTATEMENT. Let $n\ge 4$ be an integer. For a (simple, undirected) graph $G=(V,E)$ write $|V|=n$ and $\delta(G)$ for its minimum degree. Let $C_4$ denote the (not necessarily induced) 4-cycle. Define \[ f(n) := \min\big\{ d\in\{0,1,\dots,n-1\} : \text{every graph }G\text{ on }n\text{ vertices with }\delta(G)\ge d\text{ contains a }C_4\big\}. \] Question: is it true that there exists $n_0$ such that $f(n+1)\ge f(n)$ for all $n\ge n_0$? (Equivalently, letting $\Delta(n):=\max\{\delta(G): |V(G)|=n,\ G\text{ is }C_4\text{-free}\}$, we have $f(n)=\Delta(n)+1$, and the question asks whether $\Delta(n)$ is eventually nondecreasing.)

QUICK LITERATURE/CONTEXT CHECK. The problem statement notes (from a cited source) that $f(n)<\sqrt n+1$ and $f(n)=(1+o(1))\sqrt n$, and relates $f$ to the Ramsey number $R(C_4,K_{1,n})$. In what follows I do not use any external results beyond basic graph counting.

ATTACK PLAN.

• Proof track: try to relate $C_4$-free graphs with large minimum degree across successive $n$ (extension/reduction arguments), or show $\Delta(n+1)\ge \Delta(n)$ for $n$ beyond some range.
• Disproof track: search for a counterexample $n$ with $f(n+1)<f(n)$, starting with small $n$ via exhaustive computation.

WORK.

Lemma 85.1 (one-step upper Lipschitz). For every $n\ge 4$ we have \[ f(n+1)\le f(n)+1. \] Proof. Let $d=f(n)+1$ and let $G$ be any graph on $n+1$ vertices with $\delta(G)\ge d$. Pick any vertex $v\in V(G)$ and consider the induced subgraph $H:=G-v$ on $n$ vertices. Every vertex of $H$ loses at most one neighbor when $v$ is deleted, hence \[ \delta(H)\ge \delta(G)-1\ge d-1 = f(n). \] By definition of $f(n)$, $H$ contains a $C_4$, and then the same 4-cycle is also a subgraph of $G$. Thus every $(n+1)$-vertex graph with minimum degree at least $f(n)+1$ contains a $C_4$, so $f(n+1)\le f(n)+1$. $\square$

Lemma 85.2 (pair--common-neighbor bound for $C_4$-free graphs). Let $G$ be a $C_4$-free graph on $n$ vertices with minimum degree $\delta(G)=\delta$. Then \[ \delta(\delta-1)\le n-1. \] In particular, \[ f(n)\le \Big\lfloor \frac{1+\sqrt{4n-3}}{2}\Big\rfloor+1. \] Proof. In a $C_4$-free graph, any two distinct vertices $x\ne y$ have at most one common neighbor: if they had two distinct common neighbors $u\ne v$, then $x-u-y-v-x$ is a 4-cycle.

For each vertex $w\in V(G)$, the unordered pairs of neighbors of $w$ contribute $\binom{\deg(w)}{2}$ pairs $\{x,y\}\subseteq N(w)$. By the observation above, any unordered pair $\{x,y\}$ of vertices can be counted for at most one vertex $w$ (as a common neighbor), hence \[ \sum_{w\in V(G)} \binom{\deg(w)}{2} \le \binom{n}{2}. \] Using $\deg(w)\ge \delta$ for all $w$ gives \[ n\binom{\delta}{2} \le \binom{n}{2} \quad\Rightarrow\quad n\,\frac{\delta(\delta-1)}{2} \le \frac{n(n-1)}{2} \quad\Rightarrow\quad \delta(\delta-1)\le n-1. \] Now if a graph on $n$ vertices has $\delta(G)\ge d$ where $d$ is any integer with $d(d-1)>n-1$, then it cannot be $C_4$-free by the inequality just proved, so it must contain a $C_4$. Therefore $f(n)$ is at most the smallest integer $d$ with $d(d-1)>n-1$, which equals $\lfloor(1+\sqrt{4n-3})/2\rfloor+1$. $\square$

FAST REALITY CHECK (small $n$ via exhaustive search). For $4\le n\le 10$ I exhaustively searched all $C_4$-free graphs (via backtracking with an incremental "common neighbor" constraint) to compute \[ \Delta(n)=\max\{\delta(G): |V(G)|=n,\ G\text{ is }C_4\text{-free}\},\qquad f(n)=\Delta(n)+1. \] The script output was:

n=4  Delta(n)=1  f(n)=2
n=5  Delta(n)=2  f(n)=3
n=6  Delta(n)=2  f(n)=3
n=7  Delta(n)=2  f(n)=3
n=8  Delta(n)=2  f(n)=3
n=9  Delta(n)=2  f(n)=3
n=10 Delta(n)=3  f(n)=4

VERIFICATION.

• Quantifiers / definitions: $C_4$ means a 4-cycle as a (not necessarily induced) subgraph; the "two common neighbors" criterion is exactly equivalent to the presence of a $C_4$.
• Lemma 85.1 edge case: removing a vertex can only drop minimum degree by 1, so the deduction $\delta(H)\ge f(n)$ is valid.
• Lemma 85.2: checked that the counting does not assume triangle-freeness; it uses only that pairs have at most one common neighbor, which is forced by $C_4$-freeness.
• Computation: the backtracking search enforced "no pair has two common neighbors" incrementally, which is equivalent to $C_4$-freeness; results are consistent with $f(4)=2$ given in the problem statement.

FINAL. UNRESOLVED

1. (i) Strongest proved partial result. The function satisfies $f(n+1)\le f(n)+1$ for all $n\ge 4$ (Lemma 85.1), and any $C_4$-free $n$-vertex graph satisfies $\delta(\delta-1)\le n-1$ (Lemma 85.2), giving $f(n)\le \lfloor(1+\sqrt{4n-3})/2\rfloor+1$. Exhaustive search gives $f(4)=2$, $f(5)=\cdots=f(9)=3$, $f(10)=4$.
2. (ii) First gap (crisp). Show that there exists $n_0$ such that for all $n\ge n_0$ one has $f(n+1)\ge f(n)$ (equivalently, $\Delta(n+1)\ge \Delta(n)$), or else exhibit an explicit $n$ and explicit $C_4$-free graphs witnessing $f(n+1)<f(n)$.
3. (iii) Top 3 next moves.
   • Prove an extension lemma: given a $C_4$-free $n$-vertex graph with $\delta=d$, adjoin one vertex and connect it to $\ge d$ (or $\ge d-c$) vertices while preserving $C_4$-freeness.
   • Computationally push $\Delta(n)$ to larger $n$ using SAT/ILP or stronger pruning (e.g., symmetry breaking + branching on degree sequences) to look for the first potential drop.
   • Study extremal $C_4$-free graphs near the Moore-type bounds (e.g., those achieving $\delta\approx\sqrt n$) and test whether they can be "padded" without decreasing minimum degree.
4. (iv) Likely structure of a minimal counterexample. A minimal counterexample would be an $n$ such that there exists a $C_4$-free graph on $n$ vertices with minimum degree $d$ but no $C_4$-free graph on $n+1$ vertices with minimum degree $\ge d$. Heuristically this would occur at $n$ where known high-minimum-degree constructions exist only at special sizes (near "square"-type parameters), so the drop would likely be by $1$ and happen near a threshold where $d(d-1)\approx n$.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - For an $n$-vertex graph $G$, let $\delta(G)$ be its minimum degree. - Let $C_4$ denote the 4-cycle. - Define \[f(n):=\min\{d\in\mathbb N:\ \text{every graph }G\text{ on }n\text{ vertices with }\delta(G)\ge d \text{ contains a }C_4\}.\] Equivalently, \[f(n)=1+\max\{\delta(G):\ |V(G)|=n,\ G\text{ is }C_4\text{-free}\}.\]

Question. Is $f(n)$ eventually nondecreasing, i.e. does there exist $n_0$ such that $f(n+1)\ge f(n)$ for all $n\ge n_0$?

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem text only: - Asymptotically $f(n)=(1+o(1))\sqrt n$. I do not use external results from [552] here.

3) ATTACK PLAN Proof track ideas: 1. Derive general upper bounds on $f(n)$ from double-counting in $C_4$-free graphs (gives $f(n)\le \sqrt n + O(1)$). 2. Try to compare extremal $C_4$-free graphs on $n$ and $n+1$ vertices to get monotonicity up to bounded error.

Disproof track ideas: 1. Search for sporadic $n$ where the maximum possible minimum degree of a $C_4$-free graph jumps down, causing $f(n+1)<f(n)$.

Chosen path in this attempt: prove two basic $C_4$-free graph lemmas giving the elementary bound $f(n)\le \sqrt n+O(1)$, and do a small brute-force check for $n\le 7$.

4) WORK Lemma 1 (Common-neighbor bound in $C_4$-free graphs). If $G$ is $C_4$-free, then any two distinct vertices $u\ne v$ have at most one common neighbor: \[|N(u)\cap N(v)|\le 1.\]

Proof. If $u$ and $v$ had two distinct common neighbors $x\ne y$, then the four vertices $u,x,v,y$ form the cycle \[u-x-v-y-u,\] which is a $C_4$. This contradicts $C_4$-freeness. $\square$

Lemma 2 (A global constraint on 2-paths). If $G$ is $C_4$-free on $n$ vertices with degrees $d(w)$, then \[\sum_{w\in V(G)} \binom{d(w)}{2} \le \binom{n}{2}.\]

Proof. Count the set of pairs $(w,\{u,v\})$ where $u$ and $v$ are distinct neighbors of $w$ (equivalently, length-2 paths $u-w-v$ with midpoint $w$). For fixed $w$, there are $\binom{d(w)}{2}$ such unordered pairs $\{u,v\}$, so the total is $\sum_w \binom{d(w)}{2}$. On the other hand, for a fixed unordered pair $\{u,v\}$ of vertices, the number of vertices $w$ adjacent to both $u$ and $v$ is exactly $|N(u)\cap N(v)|$. By Lemma 1 this is at most $1$, so each pair $\{u,v\}$ contributes at most one triple $(w,\{u,v\})$. There are $\binom{n}{2}$ choices for $\{u,v\}$, hence the total number of such triples is at most $\binom{n}{2}$. This gives the inequality. $\square$

Corollary 3 (Elementary upper bound $f(n)\le \sqrt n+O(1)$). If $G$ is $C_4$-free on $n$ vertices, then \[\delta(G)\,(\delta(G)-1)\le n-1.\] In particular, any graph on $n$ vertices with minimum degree at least $\lfloor \sqrt{n-1}\rfloor+2$ contains a $C_4$, so \[f(n)\le \lfloor \sqrt{n-1}\rfloor+2 < \sqrt n + 2.\]

Proof. Apply Lemma 2 and use $d(w)\ge \delta(G)$ for all $w$: \[n\binom{\delta(G)}{2} \le \sum_w \binom{d(w)}{2}\le \binom{n}{2}.\] Multiply by $2/n$ to obtain $\delta(G)(\delta(G)-1)\le n-1$. If $\delta(G)\ge \lfloor \sqrt{n-1}\rfloor+2$, then $\delta(G)(\delta(G)-1)> n-1$, contradiction. Thus such a graph cannot be $C_4$-free, proving the bound on $f(n)$. $\square$

FAST REALITY CHECK (small $n$ by exhaustive search). Using brute force over all graphs for $n\le 7$, I computed the maximum possible minimum degree among $C_4$-free graphs: \[ \begin{array}{c|c|c} n & \max\{\delta(G): |V(G)|=n,\ C_4\nsubseteq G\} & f(n)\\\hline 4 & 1 & 2\\ 5 & 2 & 3\\ 6 & 2 & 3\\ 7 & 2 & 3 \end{array} \] So $f(4)=2$ and $f(5)=f(6)=f(7)=3$, consistent with monotonicity at small $n$.

5) VERIFICATION - Lemma 1 is a standard "two common neighbors create a $C_4$" argument. - Lemma 2 is a clean double-counting of 2-paths using Lemma 1. - Corollary 3 is algebraic and matches the stated asymptotic $f(n)=O(\sqrt n)$. - Computation is exhaustive only for $n\le 7$.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved an elementary upper bound $f(n)<\sqrt n+2$ via double counting (Corollary 3).

(ii) First gap: Prove eventual monotonicity $f(n+1)\ge f(n)$ (or even the bounded-drop version $f(m)\ge f(n)-c$ for $m>n$). The counting lemmas control the scale of $f(n)$ but do not compare adjacent values.

(iii) Top 3 next moves (concrete): 1. Relate $f(n)$ to the maximum minimum degree in $C_4$-free graphs and study how that extremal quantity behaves under adding a vertex with carefully chosen adjacency. 2. Use known near-extremal constructions for $\mathrm{ex}(n,C_4)$ (polarity graphs) to estimate $f(n)$ more sharply and see whether the step behavior can be controlled. 3. Compute $f(n)$ for moderate $n$ using integer programming / SAT (maximizing minimum degree under $C_4$-free constraints) to look for nonmonotone behavior.

(iv) What a minimal counterexample would likely look like (structure/parameters): An integer $n$ such that the maximum minimum degree among $C_4$-free graphs on $n+1$ vertices is strictly smaller than the corresponding maximum on $n$ vertices, forcing $f(n+1)<f(n)$.