The complete graph on \(r\) vertices is the graph Kr with \(r\) vertices in which every pair of distinct vertices are adjacent. A complete graph or, more generally, a subgraph of a graph, is often called a clique . In this section and the one that follows it, we will consider the classical problem of determining \(\ex(n,K_r)\) for \(r\geq3\text{.}\) As a warm-up, let us start by considering the special case \(r=3\) (which is known as Mantel’s Theorem). A \(K_3\)-free graph is often referred to as a triangle-free graph.

Example3.1.2.

A graph \(G\) is bipartite if \(V(G)\) can be partitioned into two sets \(A\) and \(B\) such that every edge of \(G\) has an endpoint in \(A\) and an endpoint in \(B\text{.}\) The pair \((A,B)\) are said to be a bipartition of \(G\text{.}\) We say that \(G\) is a complete bipartite graph if it contains every edge from \(A\) to \(B\text{;}\) we write \(G=K_{s,t}\) if it is complete bipartite with \(|A|=s\) and \(|B|=t\text{.}\)

It is clear that a bipartite graph cannot contain a copy of \(K_3\text{;}\) indeed, it can only contain copies of other bipartite graphs, which \(K_3\) is not. This makes a complete bipartite graph a natural candidate for trying to maximize the number of edges in a triangle-free graph. The graph \(K_{s,t}\) clearly contains \(st\) edges. Thus, among all choices of \(s\) and \(t\) with \(s+t=n\text{,}\) the number of edges in \(K_{s,t}\) is maximized when \(s\) and \(t\) are as similar as possible. Therefore,

We give a proof of Mantel’s Theorem based on the following lemma and a simple convexity argument (see Appendix C). It is important to get a good grasp of what is going on in this proof, as a similar approach will be used in several of the proofs in the rest of this chapter and the one which follows it.

We give a “combinatorial proof.” That is, our aim is to show that the quantities on the left and right sides of the equality that we are proving “count” the same set of “objects;” if this is true, then they must be equal.

The objects that we consider are triples \((x,y_1,y_2)\in V(G)^3\) such that \(xy_1\) and \(xy_2\) are both in \(E(G)\text{.}\) Perhaps the simplest way to count these objects is to

select a vertex \(x\in V(G)\text{,}\)

select a neighbour \(y_1\) of \(x\) and

select another neighbour \(y_2\) of \(x\text{.}\)

Note that we allow \(y_1\) and \(y_2\) to be the same vertex. It is not hard to see that performing these three steps precisely counts the triples \((x,y_1,y_2)\) that we are aiming to count. Thus, the number of such triples is

which is the same as the left side of the equality in the lemma. Now, suppose that we do the following instead:

select an edge \(e\in E(G)\text{,}\)

select one of the endpoints of \(e\) and call it \(x\text{,}\)

let the other endpoint of \(e\) be called \(y_1\text{,}\)

select another neighbour \(y_2\) of \(x\text{.}\)

Any triple \((x,y_1,y_2)\) of the type that we are trying to count will be chosen if and only if the edge selected in the first step is \(xy_1\text{,}\) the vertex selected in the second step is \(x\) and the vertex chosen in the fourth step is \(y_2\text{.}\) Thus, this procedure counts every such triple exactly once. Thus, the number of such triples is also equal to

Let \(G\) be a triangle-free graph. Since \(G\) is triangle-free, we have that for any edge \(uv\in E(G)\text{,}\) each vertex \(w\in V(G)\) can be adjacent to one of \(u\) or \(v\) but not both; note, this holds even in the case that \(w=u\) or \(w=v\) as no vertex is adjacent to itself. Therefore,