# small Ramsey number and Brooks' Theorem

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.

-
We capitalize names in English, e.g. Ramsey, Chvatal, Harary. Not capitalizing means disrespect. –  GH from MO Sep 26 '12 at 20:32
Than you very much GH. I'm not good at English, so I did not know that convention. If you haven't warn me, I have disrespect to their for long time. –  Yuta Suzuki Sep 27 '12 at 3:54
The adjective "abelian" is a notable exception to GH's rule. –  j.c. Sep 27 '12 at 17:21
Several mathematicians, most notably the Bourbaki school, are against naming concepts after mathematicians. In particular, they propose that names that become part of standard terminology should be de-capitalized, e.g. abelian group, galois group, noetherian ring etc. –  GH from MO Oct 5 '12 at 18:42

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.

-
Thank you very much. I'll add details my proof(?). Your proof is interesting to me. But I can't understand the sentence "This implies that some vertex of $C$ has degree 2 in $G$, since $N(v)$ only contains four vertices, a contradiction. ". Why there aren't no vertex in $N(v)$ which has two neighborhood in $S(v)$? Perhaps this is easy question, sorry. –  Yuta Suzuki Sep 27 '12 at 4:56
You are right. That part was totally unclear and misleading. I edited accordingly. –  Tony Huynh Sep 27 '12 at 15:28
Thank you very much for your edit. I was confused in "Hence, $G[N(v)]$ must be a matching $ab,cd$ of size 2" because I thought the case when c,d has two edges to $S(v)$. But by easy argument, this case can be excluded. And I can't understand (perhaps because of my weak ability of English) the sentence "Thus, every other vertex of $H$ is a stable set in $G$". Does this means "if let $C_8=v_1\dots v_8$, then $v_1v_3v_5v_7$ form stable set"? Finally, by your kindly help, we got two proofs which one is avoids Brooks' theorem, the other avoids above lemma. (to be continue) –  Yuta Suzuki Sep 27 '12 at 17:53
Then above Chvatal-Harary's proof is wrong? or not? How do you think about it? I want to know this mainly, so I can't let your answer accepted, but your answer is very helpful, so I voted up yours. –  Yuta Suzuki Sep 27 '12 at 17:56
Yes, *every other vertex of $H$* means what you think it means. It *seems* that the Chvatal-Harary proof is wrong, but I cannot say what they definitely had in mind. At the very least it is unclearly written. Finally, another idea I had in mind is to use Hadwidger's Conjecture. Since $\chi(G) \geq 4$, we have that $G$ contains a $K_4$-minor, and hence a $K_4$-subdivision $H$. Note that $H$ contains at least one subdivided edge, else $G$ contains a $K_4$. By looking at which edges of $H$ are subdivided, and how $H$ attaches to the rest of $G$, I think we can prove the theorem. –  Tony Huynh Sep 27 '12 at 22:30