##### Lemma11.1

Let \(G\) be any graph with six of more vertices. Then either \(G\) contains a complete subgraph of size \(3\) or an independent set of size \(3\text{.}\)

Bob likes to think of himself as a wild and crazy guy, totally unpredictable. Most guys do. But Alice says that Bob can't change his basic nature, which is excruciatingly boring. Carlos remarks that perhaps we shouldn't be so hard on Bob, because under certain circumstances, we can all be forced to be dull and repetitive.

Recall that when \(n\) is a positive integer, we let \([n]=\{1,2,\dots,n\}\text{.}\) In this chapter, when \(X\) is a set and \(k\) is a non-negative integer with \(k\le |X|\text{,}\) we borrow from our in-line notation for binomial coefficients and let \(C(X,k)\) denote the family of all \(k\)-element subsets of \(X\text{.}\) So \(|C([n],k)|=C(n,k)\) whenever \(0\le k\le n\text{.}\)

Recall that the Pigeon Hole Principle asserts that if \(n+1\) pigeons are placed in \(n\) holes, then there must be some hole into which two or more pigeons have been placed. More formally, if \(n\) and \(k\) are positive integers, \(t>n(k-1)\) and \(f:[t]\longrightarrow[n]\) is any function, then there is a \(k\)-element subset \(H\subseteq [t]\) and an element \(j\in[n]\) so that \(f(i)=j\) for every \(i\in H\text{.}\)

We now embark on a study of an elegant extension of this basic result, one that continues to fascinate and challenge.

Returning to the discussion at the start of this section, you might say that an induced subgraph \(H\) of a graph \(G\) is “boring” if it is either a complete subgraph or an independent set. In either case, exactly every pair of vertices in \(H\) behaves in exactly the same boring way. So is boredom inevitable? The answer is yes—at least in a relative sense. As a starter, let's show that any graph on six (or more) vertices has a boring subgraph of size three.

Let \(G\) be any graph with six of more vertices. Then either \(G\) contains a complete subgraph of size \(3\) or an independent set of size \(3\text{.}\)

We note that the bound of six in the preceding lemma is sharp, as a cycle on five vertices does not contain either a complete set of size \(3\) nor an independent set of size \(3\text{.}\)

Next, here is the statement that generalizes this result.

If \(m\) and \(n\) are positive integers, then there exists a least positive integer \(R(m,n)\) so that if \(G\) is a graph and \(G\) has at least \(R(m,n)\) vertices, then either \(G\) contains a complete subgraph on \(m\) vertices, or \(G\) contains an independent set of size \(n\text{.}\)