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.

  • $\begingroup$ We capitalize names in English, e.g. Ramsey, Chvatal, Harary. Not capitalizing means disrespect. $\endgroup$
    – GH from MO
    Sep 26, 2012 at 20:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – snufkin26
    Sep 27, 2012 at 3:54
  • $\begingroup$ The adjective "abelian" is a notable exception to GH's rule. $\endgroup$
    – j.c.
    Sep 27, 2012 at 17:21
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Oct 5, 2012 at 18:42
  • $\begingroup$ ...also hilbert space. Unnecessary capital letters are eyesores. $\endgroup$
    – Wlod AA
    Jul 13, 2017 at 22:08

1 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.

  • $\begingroup$ 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. $\endgroup$
    – snufkin26
    Sep 27, 2012 at 4:56
  • $\begingroup$ You are right. That part was totally unclear and misleading. I edited accordingly. $\endgroup$
    – Tony Huynh
    Sep 27, 2012 at 15:28
  • $\begingroup$ 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) $\endgroup$
    – snufkin26
    Sep 27, 2012 at 17:53
  • $\begingroup$ 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. $\endgroup$
    – snufkin26
    Sep 27, 2012 at 17:56
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Sep 27, 2012 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .