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.



Small Ramsey numbers and Brooks' Theorem
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. 


