Small Ramsey numbers and Brooks' Theorem

Question

I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. Small off-diagonal numbers, Pacific Journal of Mathematics 41, No.2, 1972, pp.335-345), I can't understand the proof of $r(C_4,K_4)=10$. Their proof is like following.

Let $G$ is arbitrary simple graph of order 10 with point independence number $<4$. It is sufficient to prove $G$ contains $C_4$. From $G$'s point independence number is $<4$, $G$'s (point) chromatic number is $\ge4$. Hence by Brooks' theorem either $K_4$ (and hence $C_4$) is contained in $G$, or the degree of each point of $G$ is at least four. If the first case occur, we have done. If the second case occur, we also have $C_4$ in $G$ by the following lemma (I omit the proof of this lemma but it's not so difficult).

Lemma. If a graph $G$ with $p$ points has minimum degree $d$ and $d(d-1)>p-1$, then $G$ contains $C_4$.

I can't understand how to use Brooks' Theorem. I only succeed to derive the maximum degree of $G$ is greater than 3. How to derive that the minimum degree of $G$ is greater than 3 from Brooks' Theorem? Chvatal and Harary's proof is wrong as it is? or not? (If you have other elegant proof of $r(C_4,K_4)=10$, then It also help me.)

supplementation:I got a (awkward?) proof of $r(C_4,K_4)=10$. The proof is like following.

For lower bound, we use Chvatal-Harary theorem.

For upper bound, we think about above graph $G$. Using $r(C_4,K_3)=7$, easily we have there is no vertex with degree $\le2$. By lemma, we have at least one vertex (say $u$) whose degree is 3.

Claim. The subgraph induced by vertices non-adjacent to $u$ contains $2K_3$.

The subgraph induced by vertices non-adjacent to $u$ has 6 vertices. So we have two triangles $T_1,T_2$ in this subgraph. If $T_1,T_2$ has two common vertex, we get $C_4$. If $T_1,T_2$ has only one common point, let $T_j=v_0v_1^jv_2^j$. Let $w$ be the other vertex non-adjacent to $u$. Then $v_2^1w$ isn't an edge by symmetry and avoiding $C_4$, namely $v_0v_1^1wv_2^1$. We also have edge $v_1^2w$ by avoiding 4 independent vertices $v_2^1wv_1^2u$.By symmetry, we have $C_4$, namely $v_0v_1^2wv_2^2$ and it's a contradiction.

Claim. The neighborhood subgraph $N(u)$ of $u$ is $\bar{K_3}$.

If not, the neighborhood subgraph of $u$ is an isolated vertex $v_1$ and an edge $v_2v_3$. $v_2$ and $v_3$ has at least one edge to $T_1\cup T_2$, since their degree $\ge3$. If $v_2$ and $v_3$ has edges to common triangle, we get $C_4$. So if we let $T_j=w_1^jw_2^jw_3^j$, we can assume there are edges $v_2w_1^1, v_3w_1^2$. ($v_1,v_2$ has no other edges to $T_1\cup T_2$.) Then both edges $v_1w_2^1,v_1w_3^1$ cannnot be exist. So we can assume there isn't edge $v_1w_3^1$, then we have edge $w_3^1w_1^2$, since otherwise we have 4 independent vertices $v_1v_2w_3^1w_1^2$. By symmetry, we also have edge $w_1^1w_3^2$. So we have $C_4$, $w_1^1w_3^2w_1^2w_3^1$. It's a contradiction.

Now, we have $T_j=w_1^jw_2^jw_3^j$ and 6 edges $v_iw_i^j$. Then we have edge $w_1^1w_1^2$, since otherwise $w_1^1w_1^2v_2v_3$ form 4 independent vertices. By symmetry, we have $C_4$, namely $w_1^1w_1^2w_2^2w_2^1$. It's a contradiction.

Answer 1

It seems as if the Chvatal, Harary proof has a logical gap, and your proof seems to be missing some details.

Here is a proof that is based on Brook's Theorem. We plagiarize you and start by noting that $r(C_4,K_3)=7$, and so $G$ has minimum degree at least 3. We then plagiarize Chvatal, Harary and note that $G$ has chromatic number at least 4. Thus, by Brook's Theorem, $G$ has maximum degree $\Delta(G)$ at least 4. Let $v$ be a vertex of maximum degree and let $N(v)$ be the neighbours of $v$ and let $S(v)$ be the non-neighbours of $v$. Since $G$ has no $C_4$, note that each vertex in $S(v)$ has at most one neighbour in $N(v)$. Thus, the minimum degree of the subgraph induced by $S(v)$ is at least 2. This rules out $\Delta(G)=9,8$, or $7$.

If $\Delta(G)=6$, then there are at least three vertices $x,y,z \in N(v)$ which are not adjacent to any vertex in $S(v)$. Since $x$ has degree at least 3 in $G$, it must be adjacent to at least two other vertices in $N(v)$, which creates a $C_4$.

If $\Delta(G)=5$, then $G[S(v)]$ is a graph on 4 vertices with minimum degree 2. Such a graph necessarily contains a $C_4$.

We now suppose $\Delta(G)=4$. In this case, $G[S(v)]$ is a graph on 5 vertices with minimum degree 2. Thus, every cycle of $G[S(v)]$ must be of length 3 or 5. If $G[S(v)]$ contains a $C_5$, then $G[S(v)]=C_5$, since adding any chord to a $C_5$ produces a $C_4$. Thus, each vertex in $G[S(v)]$ has exactly one neighbour in $N(v)$. Hence, $G[N(v)]$ must be a matching $\{ab, cd\}$ of size 2, else $G$ has a vertex of degree 2. It follows that each vertex in $N(v)$, has at least one neighbour in $S(v)$. Thus, one vertex (say $a$) has exactly two neighbours in $S(v)$, while $b,c$, and $d$ have exactly one neighbour in $S(v)$. Let $x,y,z$ be the vertices in $S(v)$ which are not adjacent to either $b$ or $c$. If any of $xy,yz,xz \notin E(G)$, then $G$ has a stable set of size 4. Thus, $xyz$ is a triangle. This contradicts that $G[S(v)]=C_5$.

The only remaining possibility is that $G[S(v)]$ is a bowtie. In particular, $G$ has two non-adjacent vertices $u$ and $v$ of degree 4 such that $N(u)$ and $N(v)$ are disjoint. Thus, the subgraph $H$ of $G$ induced by $N(u) \cup N(v)$ has minimum degree at least 2. In particular $H$ contains a cycle $C$. It is easy to verify that if $|C|=3,4,5,6,$ or $7$, then $G$ contains a $C_4$ since $H$ cannot contain a vertex with two neighbours in $N(u)$ or two neighbours in $N(v)$. Thus, $|C|=8$. But then $H=C_8$ else $H$ contains a cycle of smaller length. Thus, every other vertex of $H$ is a stable set in $G$, a contradiction.

Note that this proof avoids the use of the minimum degree lemma.