The Extremal Number of a Triangle

Section 3.1 The Extremal Number of a Triangle

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.

Figure 3.1.1. The complete graphs \(K_1,K_2,K_3,K_4,K_5\) and \(K_6\text{.}\)

Example 3.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,

\begin{equation*} \ex(n,K_3) \geq \left\lfloor \frac{n}{2}\right\rfloor\left\lceil \frac{n}{2}\right\rceil = \left\lfloor \frac{n^2}{4}\right\rfloor \end{equation*}

for all \(n\text{.}\)

Figure 3.1.3. The complete bipartite graphs \(K_{3,3}\) and \(K_{2,4}\text{.}\)

As it turns out, Example 3.1.2 is tight.

Theorem 3.1.4. Mantel’s Theorem [213].

If \(G\) is a triangle-free graph, then

\begin{equation*} |E(G)|\leq\frac{|V(G)|^2}{4}\text{.} \end{equation*}

Consequently,

\begin{equation*} \ex(n,K_3)= \left\lfloor \frac{n^2}{4}\right\rfloor \end{equation*}

for all \(n\text{.}\)

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.

Lemma 3.1.5.

For any graph \(G\text{,}\)

\begin{equation*} \sum_{v\in V(G)}\degree(v)^2 = \sum_{uv\in E(G)}(\degree(u)+\degree(v))\text{.} \end{equation*}

Proof.

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 are counting are “walks” of length two in the graph. That is, we are counting triples \((v_1,v_2,v_3)\) such that \(v_1v_2\in E(G)\) and \(v_2v_3\in E(G)\text{.}\) One way of counting these triples is by first choosing the central vertex \(v_2\) and then choosing \(v_1\) and \(v_3\) to be neighbours of it. For any \(v\in V(G)\text{,}\) the number of choices for either of \(v_1\) or \(v_3\) given that \(v_2=v\) is equal to the degree of \(v\text{.}\) So, the number of such triples is

\begin{equation*} \sum_{v\in V(G)}\degree(v)^2 \end{equation*}

which is the same as the left side of the equality in the lemma. Now, we count it in another way. First, pick an edge \(uv\in E(G)\text{.}\) Then, choose one of the endpoints to be \(v_1\) and let the other endpoint be \(v_2\text{.}\) Finally, choose a neighbour of \(v_2\) to be \(v_3\text{.}\) This counts the same thing. Thus, the number of paths of length two can also be represented by

\begin{equation*} \sum_{uv\in E(G)}(d(u)+d(v))\text{.} \end{equation*}

This completes the proof.

Proof of Theorem 3.1.4.

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,

\begin{equation*} \degree(u)+\degree(v) \leq |V(G)| \end{equation*}

for any \(uv\in E(G)\text{.}\) By Lemma 3.1.5 and the above inequality,

\begin{equation*} \sum_{v\in V(G)}\degree(v)^2 = \sum_{uv\in E(G)}(\degree(u)+\degree(v))\leq |E(G)|\cdot|V(G)|\text{.} \end{equation*}

By the standard “handshaking lemma,” we have

\begin{equation*} \sum_{v\in V(G)}\degree(v)=2|E(G)|\text{.} \end{equation*}

Putting this all together and applying Corollary C.0.6, we obtain

\begin{equation*} 4|E(G)|^2 = \left(\sum_{v\in V(G)}\degree(v)\right)^2 \leq |V(G)|\cdot \sum_{v\in V(G)}\degree(v)^2 \leq |V(G)|^2\cdot|E(G)|\text{.} \end{equation*}

The result follows by dividing both sides by \(4|E(G)|\text{.}\)

Here are a couple of YouTube videos related to Mantel’s Theorem:

Prev Top Next