Every $C_4$-free graph on $49$ vertices has a vertex of degree at most $6$

Technical assistance: Claude (Anthropic)

Introduction

For $n \ge4$ let $f(n)$ be the least integer such that every graph on $n$ vertices with minimum degree at least $f(n)$ contains a cycle $C_4$, and let $h(n) = f(n) - 1$ be the largest minimum degree of a $C_4$-free graph on $n$ vertices. Erdős asked whether $f(n+1) \ge f(n)$ for all sufficiently large $n$, and whether at least $f(m) > f(n) - c$ for all $m > n$ and some constant $c$ (Problem 85 of [2], where the original sources, among them [3 p. 345], are listed).

The function $f$ carries the same information as the Ramsey number $s(m) = R(C_4,K_{1,m})$: a $C_4$-free graph on $N$ vertices whose complement contains no $K_{1,m}$ is exactly a $C_4$-free graph with minimum degree at least $N - m$, so that

Parsons [5] proved $s(m) \le m + \lfloor\sqrt{m-1}\rfloor+ 2$ for all $m \ge2$ (see [1]). The values of $s(m)$ are known for $m \le38$ [1, 7], and also $s(40) = 47$; the values $s(38) = 45$ and $s(40) = 47$ are due to Zhang, Chen and Cheng [6]. The tables of [1] and [7] record $s(41)=49$; we did not find a construction for the lower bound $s(41)\ge49$ in [1, 5, 7]. For $m=42$ the table of [1] gives only the upper bound 50, the lower bound 49 following from $s(41)\ge49$ (or from [1 Remark 12]).

Status of the statements. Theorem 1 is proved by Lemmas 3–6, the reduction of Section 4 (proved by hand) and a finite computation (Section 5), carried out by two separately written programs. In Corollary 2, the values $f(48)=f(50)=8$ and $R(C_4,K_{1,41})=49$ are proved from explicit graphs, independently of Section 5; $f(49)=7$ and $R(C_4,K_{1,42})=49$ rest on Theorem 1. The question of Problem 85, monotonicity for all large $n$, remains open.

A counting lemma

All graphs are finite and simple. For a vertex $x$, $N(x)$ is its neighbourhood and $d(x)$ its degree. In a $C_4$-free graph two distinct vertices have at most one common neighbour.

Proof. If $y\in N(x)$ had two neighbours $w,w'\in N(x)$, then $xwyw'$ would be a $C_4$; so the edges inside $N(x)$ form a matching. A vertex $z\notin N[x]$ with two neighbours in $N(x)$ would close a $C_4$ through $x$. Hence the sets $N(y)\setminus\{x\}$, $y\in N(x)$, cover each vertex at distance 2 exactly once and each vertex of $N(x)$ that lies on an edge inside $N(x)$ exactly once, which gives the formula.

The structure for $k^2$ vertices, $k$ odd

Fix an odd integer $k\ge3$ and let $G$ be a $C_4$-free graph on $k^2$ vertices with minimum degree at least $k$.

Proof. For a vertex $x$ of degree $r$, Lemma 3 with $d(y)\ge k$ and $T(x)\le r/2$ gives $k^2\ge1+r+r(k-1)-r=1+r(k-1)$, so $r\le k+1$. The degree sum is even, while $k\cdot k^2$ is odd; hence not all degrees equal $k$, which proves (i). If $d(v)=k+1$, equality must hold throughout: $T(v)=(k+1)/2$, every neighbour of $v$ has degree $k$, and every vertex lies within distance 2 of $v$; this is (ii), and (iii) follows from it. For (iv), if $d(x)=k$ and $t$ neighbours of $x$ have degree $k+1$, Lemma 3 gives

so $2T(x)\ge1+t\ge1$.

From now on $v$ is a vertex of degree $k+1$, $N(v)=\{u_1,\ldots,u_{k+1}\}$ with the matching $u_{2i-1}u_{2i}$, and $G_i=A_{u_i}$. We call $G_i$ and $G_{i'}$ partner groups when $u_i u_{i'}$ is an edge. The vertices of $\bigcup G_i$ are the outer vertices and $H$ is the graph they induce.

Proof. Each statement is the exclusion of an explicit 4-cycle: (a) $u_i y x y'$; (b) $x u_i u_{i'} y$; (c) $x y u_j y'$; (d) $x z y u_i$; (f) follows from (a)–(c) and $d(x)\ge k$, since $x$ has at most $k$ possible neighbours in $H$ (one in its own group and one in each of the $k-1$ groups that are neither its own nor its partner).

For the converse, let $C$ be a 4-cycle of the whole graph and let $j$ be the number of its vertices in $N[v]$. If $v\in C$, its two neighbours on $C$ are some $u_i,u_l$, and the fourth vertex is a common neighbour of $u_i,u_l$ other than $v$: it is not in $N(v)$ (the edges inside $N(v)$ form a matching) and not outer (an outer vertex has one neighbour in $N(v)$); impossible. So $v\notin C$. If $j=0$, $C$ lies in $H$, excluded by (e). If $j\ge1$, every vertex $u_i$ of $C$ has its two $C$-neighbours in $\{u_{i'}\}\cup G_i$, where $u_{i'}$ is its partner. If $C$ contains an edge $u_i u_{i'}$, the other two vertices are $x\in G_i$ and $y\in G_{i'}$ adjacent in $H$, excluded by (b). Otherwise every vertex of $C$ in $N(v)$ has both $C$-neighbours in its own group; two such vertices $u_i,u_l$ on $C$ would be opposite, with $C$-neighbours in $G_i\cap G_l=\varnothing$, so $j=1$ and $C=u_i x z y$ with $x,y\in G_i$ and $z$ a common neighbour of $x,y$ in $H$, excluded by (d). Finally the degrees: an outer vertex has degree $1+d_H(x)\ge k$, the $u_i$ have degree $k$ and $v$ has degree $k+1$.

We say that an outer vertex has $k$ slots: its own group and the $k-1$ groups that are not partners of its group. By (a)–(c) it has at most one neighbour per slot, and by (f) at most one empty slot; it has degree $k+1$ in $G$ exactly when no slot is empty.

Proof. Each $z\in W$ has at most one common neighbour with $x$, and none outside $H$, because the only neighbour of $z$ in $N[v]$ is the vertex attached to $W$, which is not adjacent to $x$.

Symmetry reduction

Fix $k=7$, a vertex $v$ of degree 8 (Lemma 4), the matching $u_1u_2,u_3u_4,u_5u_6,u_7u_8$ of $N(v)$ and the groups $G_1,\ldots,G_8$ of five outer vertices each. The labelling of $N(v)\cup\bigcup G_i$ is free subject to the matching; we fix it in four steps, each of which can be achieved by relabelling any solution, so that a solution exists if and only if a solution satisfying all four conditions exists.

Step 1 (reference group). Exactly one of the following holds. Case I: some outer vertex has degree 8; we let $G_1$ be a group containing one. Case II: no outer vertex has degree 8; we let $G_1$ be a group with the fewest edges inside it. In both cases $G_2$ denotes the partner of $G_1$.

Step 2 (order of the other groups). The 48 relabellings of $G_3,\ldots,G_8$ that preserve the partner pairs $\{G_3,G_4\},\{G_5,G_6\},\{G_7,G_8\}$ are applied so that $m_3\ge m_4$, $m_5\ge m_6$, $m_7\ge m_8$ and $m_3\ge m_5\ge m_7$, where $m_w$ is the number of edges between $G_1$ and $G_w$.

Step 3 (inside $G_1$). The vertices of $G_1$ are numbered $0,\ldots,4$ so that the edges inside $G_1$ are among $\{0,1\},\{2,3\}$, with $\{0,1\}$ used first.

Step 4 (alignment). For $w=3,\ldots,8$ the vertices of $G_w$ are numbered so that those with a neighbour in $G_1$ come first, in the order of their neighbour; $G_2$ is numbered in the same way with respect to $G_3$. By Lemma 5(c) the edges between two non-partner groups form a matching, so this is always possible, and it leaves no freedom inside the matched part. After these steps the adjacency of $G_1$ to the whole outer graph is determined by its pattern: the edges inside $G_1$ and, for every vertex of $G_1$, its empty slot if any. Two patterns are equivalent when they differ by a permutation of the five vertices of $G_1$ and by one of the 48 relabellings of Step 2; Steps 3–4 then restore the normal form. A direct enumeration gives 39 equivalence classes of patterns, 18 of which contain a vertex without empty slot and 21 of which do not; in Case I only the former can occur for $G_1$, in Case II only the latter. For each class one representative is fixed (for Program A one compatible with Steps 2–4); the corresponding sub-problems are the cubes.

Proof. For a group $X$ and a group $Y$ that is neither $X$ nor its partner, let $D(X,Y)$ be the number of vertices of $X$ whose empty slot is $Y$. Every vertex of $X$ has exactly one neighbour in $Y$ unless its empty slot is $Y$, so there are $5-D(X,Y)$ edges between $X$ and $Y$, and $D(X,Y)=D(Y,X)$. A vertex has its own slot empty exactly when it lies on no edge inside its group (the edges inside a group form a matching), so the $2i(X)$ vertices of $X$ on such edges are those whose empty slot is another group: $\sum_Y D(X,Y)=2i(X)$. Hence the number of vertices outside $X$ whose empty slot is $X$ is $\sum_Y D(Y,X)=2i(X)$. A pair $(x,z)\in A\times A'$ has no common neighbour in $N[v]\cup A\cup A'$ (there are no edges between $A$ and $A'$) and at most one common neighbour in all. A vertex $w$ of one of the six other groups $C$ is adjacent to a vertex of $A$ and to a vertex of $A'$ unless its empty slot is $A$ or $A'$; distinct such $w$ give distinct pairs. Hence $25\ge\sum_C(5-D(C,A)-D(C,A'))=30-2i(A)-2i(A')$. □

Computation

Additional valid constraints. Besides Lemma 5, the following constraints are imposed. The first two are consequences of Lemmas 4 and 6 and hold in every solution. The Case II items express the choice of $G_1$ in Step 1 and two refinements of it; they hold in a suitably relabelled copy of every solution, because the quantities used for the choice (the number of inner edges of a group, the number $c(G)$ and the type defined below) do not change under the relabellings of Steps 2–4.

• (Triangles) every outer vertex lies on a triangle (Lemma 4(iv), and for an outer vertex of degree 8 part (ii) applied to it);

• (Pigeonhole) Lemma 6 for every outer vertex $x$ and every group $W$;

• (Case II) every outer vertex has exactly one empty slot, and every group has at least as many inner edges as $G_1$;

• (Case II, two inner edges in $G_1$) then every group has exactly two inner edges and exactly one vertex whose empty slot is its own group, the other four having their empty slot in another group. Among the groups, $G_1$ is chosen to maximise $c(G)$, the largest number of vertices of $G$ with the same empty slot. If $A,B$ are non-partner groups, the vertices of $A$ with a neighbour in $B$ are those whose empty slot is not $B$, so the number of edges between $A$ and $B$ is at least $5-c(A)\ge5-c(G_1)$. This lower bound is imposed for all such pairs (by Program A in 14 of the 17 cubes of this kind, by Program B in all of them).

• (Case II, one inner edge in $G_1$) then every group has one or two inner edges. If a group $A$ has exactly one inner edge $xy$, its three other vertices have their empty slot in $A$, and $x,y$ have their empty slots in groups $b_x,b_y$ different from $A$ and its partner; hence $m(A,B)=5-[b_x=B]-[b_y=B]$ for every group $B$ that is not $A$ or its partner, where $m(A,B)$ is the number of edges between $A$ and $B$. Say $A$ has type $\alpha$ if $b_x=b_y$, type $\beta$ if $b_x,b_y$ are partner

groups, and type $\gamma$ otherwise. Among the groups with one inner edge, $G_1$ is chosen of the highest type ($\alpha> \beta> \gamma$). If $G_1$ has type $\beta$, no group with one inner edge has type $\alpha$, i.e. $m(A,B) \ge4$ for all such $A$ and all groups $B$ other than $A$ and its partner; if $G_1$ has type $\gamma$, in addition $m(A,B) + m(A,B') \ge9$ for every partner pair $B,B'$ of groups different from $A$ and its partner. These implications are imposed through one switch variable $s_A$ per group: $s_A$ true forces at least two inner edges in $A$, $s_A$ false forces at most one inner edge in $A$ and the conditions above; the bound $i(A) + i(A') \ge3$ of Lemma 7 is also imposed for the cubes of types $\beta$ and $\gamma$. Some nodes of the search trees of these cubes were refuted on formulas containing only part of these clauses; a refutation of part of the clauses is a refutation of the whole formula.

The choices of $G_1$ (Case I or II; fewest inner edges; then largest $c$ or highest type) are made in this order, before Steps 2–4, and do not use any freedom used later.

Program A. The whole graph on 49 vertices is encoded in propositional logic, one variable per pair of vertices, with the structure of Lemma 4(ii) fixed, all 4-cycles forbidden, degree constraints encoded by sequential counters, and the constraints of Section 4 and above. For each of the 39 cubes the formula is either refuted directly by KISSAT, or split by the look-ahead solver MARCH_CU into sub-cubes, i.e. lists of literals added as unit clauses. Every split is accepted only together with a covering check: a run on the parent formula with the negations of all sub-cubes added as clauses. Sub-cubes are refuted separately, by KISSAT or by an incremental CaDiCaL run under assumptions, within CPU-time limits, or by CaDiCaL 3.0.1 within a limit on the number of conflicts. A sub-cube exceeding its limit is either split again in the same way or refuted later by a single longer run; a set of literals contained in several sub-cubes may also be refuted directly, which refutes all of them. A node of this search tree is thus refuted when it is refuted directly, when it contains a refuted set of literals, or when its covering check and all its children are refuted. Every run on which the proof relies returned UNSATISFIABLE, and no run returned SATISFIABLE (the other runs stopped at their time or conflict limit, or were interrupted).

Program B. The second program encodes only the outer graph $H$ through conditions (a)–(f) of Lemma 5 (every solution gives such an $H$, and by the converse part of the lemma nothing is lost). It has its own implementation of the alignment of Step 4, it does not use Step 2, and it takes as representative of each of the 39 pattern classes the lexicographically least element of the class. It has its own implementation of the triangle, pigeonhole and Case II conditions, and solves with CaDiCaL, with the same tree rules (splits by MARCH_CU with covering checks, CPU-time limits, longer direct runs) implemented in a separate job manager. For the three cubes of Case II with one inner edge in $G_1$, part of the search tree was refuted on the formula augmented by static symmetry breaking. Some relabellings of the outer vertices map such a cube to itself and fix $G_2$ and $G_3$ pointwise: the swaps of whole groups among $G_5,\ldots,G_8$ that preserve the partner pairs and the adjacency to $G_1$, and, in the cube of type $\alpha$, the swap of the two ends of the inner edge of $G_1$ together with the swap of the matching positions in the groups matched to them. Since all other constraints are stated uniformly, such a relabelling $\pi$ maps solutions to solutions, and the lexicographic-leader clauses $E \le E \circ\pi$ (edge variables in a fixed order) keep the least solution of every orbit. A node refuted on the original formula is refuted a fortiori on the augmented one, so the tree refutes the augmented formula, which is satisfiable whenever the cube formula is. In cubes 4 and 5 the exact switch variables and the bound of Lemma 7 are added on top of these clauses; every solution satisfies them once $s_A$ is set to true exactly when $A$ has at least two inner edges, and they are stated uniformly over the groups and the partner pairs, so the relabellings $\pi$ still map solutions to solutions, and the least solution of every orbit satisfies all the added clauses. The two programs share the reduction of Sections 2–4, which is proved by hand, the derived constraints, the authors and the solver CaDiCaL, so they are not independent in every respect; they differ in the encoding, in the implementation of the symmetry breaking and in the representatives of the classes.

Runs. The logs of Program A record 6 684 refutations (covering checks included) and 362 runs stopped at their limit; those of Program B record 1 122 and 149. The runs were made on two machines, a Linux server and a desktop computer under Windows. The runs marked W in the logs (2 179 refutations) were distributed as separate tasks, to the desktop computer or, where marked W:cadical-server, to the server. All of them except 63 short ones were made by CaDiCaL 3.0.1 with a limit of 4 million conflicts (15 million for cube 5 of Program B); the 63 others, marked W alone, were made by a solver of python-sat whose name was not logged, and all of them were certified (Checks (iv)). For each of these runs the literals of the leaf were regenerated from the logged splits and compared with the literals sent to the solver before the result was entered in the log. The other runs used kissat 4.0.4 and the versions of CaDiCaL included in python-sat.

Checks. (i) The 36 506 patterns fall into 39 classes (18 in Case I), and the cubes of each program contain exactly one pattern of each class; this is verified by two scripts, one computing canonical forms (for the patterns whose inner edges are $\varnothing$, $\{0,1\}$ or $\{0,1\},\{2,3\}$, which meet every class) and one computing the classes of all patterns by union–find from generators of the acting group. (ii) Falsification: with the minimum degree condition weakened to 6 for the outer vertices and everything else unchanged, 17 formulas of both programs, among them formulas of every kind used (cubes of Case I and of Case II, including the cubes of types $\alpha$, $\beta$ and $\gamma$, with and without the symmetry-breaking and exact switch clauses), become satisfiable within seconds, and every model found is decoded into a $C_4$-free graph on 49 vertices with minimum degree 6, checked directly. (iii) The Hoffman–Singleton graph (50 vertices, 7-regular, girth 5) is accepted by the graph checker. (iv) Proof certificates: for a fixed random sample of refuted nodes with short logged runs (67 nodes, 6 of Program A and 61 of Program B), the formula was rebuilt from the scripts, solved again by kissat with a DRAT proof, and every proof was verified by the independent checker drat-trim. In separate runs (not part of the ancillary scripts), 76 further leaves refuted by runs marked W were certified in the same way: the 63 marked W alone, and 13 others (12 of Program A, 1 of Program B), 10 of them drawn at random. (v) A separate script reads the logs of both programs and checks that every cube is refuted according to the rules above. (vi) For the symmetry breaking of Program B, a script checks that every relabelling used is an involution preserving groups and partner pairs, maps the fixed literals of the cube to themselves and fixes $G_2$ and $G_3$ pointwise; on the formulas with weakened minimum degree it checks moreover that models are mapped to models and that the augmented formulas stay satisfiable.

The scripts are pure Python and are provided as ancillary files, together with the list of cubes, the solver logs and the SHA-256 hashes of all formulas used.

Proof of Corollary 2

$f(50)=8$. The Hoffman–Singleton graph [4] has 50 vertices, is 7-regular and has girth 5, so $h(50)\ge7$. A vertex of degree $r\ge8$ in a $C_4$-free graph with minimum degree 8 would satisfy $1+r+7r-2T(x)\le50$ by Lemma 3, i.e. $2T(x)\ge8r-49\ge15$, which is impossible since $T(x)\le r/2$ forces $8r-49\le r$, i.e. $r\le7$. Hence $h(50)\le7$ and $f(50)=8$.

$f(48)=8$. Let $SD_{16}=\langle a,x\mid a^8=x^2=1,\ xax^{-1}=a^3\rangle$ be the semidihedral group of order 16, let $c$ generate $C_3$, and let $\Gamma$ be the Cayley graph of $SD_{16}\times C_3$ with respect to the inverse-closed set

$\Gamma$ has 48 vertices and is 7-regular. It is $C_4$-free: a Cayley graph $\operatorname{Cay}(G,S)$ contains a 4-cycle if and only if $st^{-1}=s't'^{-1}$ for two distinct ordered pairs $(s,t)\ne(s',t')$ with $s\ne t$, $s'\ne t'$, and the 42 elements $st^{-1}$ ($s\ne t$) are pairwise distinct. (The edge list is provided and checked by two independent programs.) Hence $h(48)\ge7$. Conversely, by Lemma 3, a $C_4$-free graph on 48 vertices with minimum degree 8 would give, for a vertex $x$ of degree $r \ge8$, $1+r+7r-2T(x) \le48$ with $2T(x) \le r$, i.e. $7r \le47$, a contradiction. So $h(48)=7$ and $f(48)=8$. In terms of Ramsey numbers, $h(48) \ge7$ means $s(41) \ge49$, and with the upper bound $s(41) \le41+\lfloor\sqrt{40}\rfloor+2=49$ of [5] this gives $R(C_4,K_{1,41})=49$.

$f(49)=7$. Theorem 1 gives $h(49) \le6$. Deleting one vertex of the Hoffman–Singleton graph leaves a $C_4$-free graph on 49 vertices with minimum degree 6, so $h(49)=6$ and $f(49)=7$. In terms of Ramsey numbers, $h(49) \le6$ means $s(42) \le49$, and $s(42) \ge s(41)=49$; hence $R(C_4,K_{1,42})=49$.

Remarks

1. Problem 85 of [2] asks whether $f(n+1) \ge f(n)$ for all sufficiently large $n$. A single exception does not settle that question, which remains open; the result above only shows that $f$ is not non-decreasing on all $n \ge4$.

2. By the equivalence $h(N) \ge N-m \Longleftrightarrow s(m) \ge N+1$, an index $N \ge4$ with $f(N+1)<f(N)$ exists if and only if $s(m)=s(m+1)$ for some $m \ge2$ (then $N=s(m)-1$). By the tables of [7] (and [1]), $s(m)<s(m+1)$ for $2 \le m \le38$ and for $m=40$, while [7] gives $s(39) \in\{46,47\}$; the value $s(39)=47$ would give the smaller instance $f(47)<f(46)$.

3. In terms of Ramsey numbers the two results read $R(C_4,K_{1,41})=R(C_4,K_{1,42})=49$. The value 49 for $n=41$ appears in the tables of [1] and of the dynamic survey of Radziszowski; the graph $\Gamma$ of § 6 gives an explicit lower-bound construction for it. Erdős also asked whether consecutive values of $R(C_4,K_{1,n})$ coincide for infinitely many $n$ (Problem 552 of [2]); $n=41$ is an instance.

4. In $\Gamma$ every vertex has exactly three edges in its neighbourhood: the 48 triangles form a configuration $(48_3)$ whose collinearity graph is $C_4$-free, and the remaining 24 edges form a perfect matching.

5. The page of Problem 85 in [2] states that the bounds of Problem 552 imply $f(n)<\sqrt{n}+1$. This inequality fails for some $n$, already for $n=15$: the line graph of the Petersen graph is 4-regular and $C_4$-free, so $f(15) \ge5>\sqrt{15}+1$ (in fact $f(15)=5$ by the bound below); it also fails for $n=48$: $f(48)=8>\sqrt{48}+1\approx7.93$. Lemma 3 gives $\delta(\delta-1) \le n-1$ for the minimum degree $\delta$ of a $C_4$-free graph on $n$ vertices, hence only $f(n)<\sqrt{n}+3/2$.