5 Extremal Combinatorics 5.1 Erdös-Szekeres lemma and Dilworth’s theorem 5.3 Ramsey Theory and Probabilistic method

5.2 Existence of complete subgraphs

Lemma 5.4.

Every graph has a self-avoiding walk of length $\delta(G)$ .

Proof.

WLOG assume $\delta(G)\geq 1$ . Let $v_{0}$ be a vertex in $G$ . Given $v_{i},i<\delta(G)$ , we can choose a neighbour $v_{i+1}$ of $v_{i}$ such that $v_{i+1}\neq v_{0},\ldots,v_{i-1}$ as $v_{i}$ has at least $\delta(G)$ neighbours. Hence we get a self-avoiding walk $v_{0}v_{1}\ldots v_{\delta(G)}$ as needed. ∎

Define girth of a graph $g(G):=\min\{l(C):C,\mbox{a cycle}\}.$ Set $g(G)=\infty$ if there exists no cycle. The diameter of a graph if $\operatorname{diam}(G)\coloneqq\max\{d(u,v):u,v\in V\}$ and

Lemma 5.5.

If $G$ has a cycle, $g(G)\leq 2\operatorname{diam}(G)+1$ .

Proof.

Assume otherwise. Let $C=v_{0}\ldots v_{k}v_{0}$ be the cycle of minimal length. Suppose $k$ is even i.e., $\ell(C)=k+1$ is odd. Then $d(v_{0},v_{k/2})=k/2$ . But by definition of diameter, $k/2\leq\operatorname{diam}(G)$ and so $\ell(C)=k+1\leq 2\operatorname{diam}(G)+1$ . If $k$ is odd then $d(v_{0},v_{(k+1)/2})=k+1/2$ and again we have that $\ell(C)=k+1\leq 2\operatorname{diam}(G)$ . ∎

Lemma 5.6 (Mantel’s theorem, 1907).

If $G$ is a graph on $n$ vertices with no triangle then $|E|\leq\lfloor n^{2}/4\rfloor$ . Equivalently, if $|E|>n^{2}/4$ , then $g(G)=3$ .

We shall give a proof via a weight-shifting argument. Three other proofs can be found in [Jukna 2011, Section 4.3]. We will next prove Turan’s theorem using induction and the same will also work for Mantel’s theorem. Other applications of weight-shifting argument are in [Jukna 2011, Section 4.7].

Proof.

(Motzkin-Straus, 1965) Let $G$ have $[n]$ has a vertex set and no triangles. Let $z_{i}\geq 0$ be weight of $i$ such that $\sum_{i}z_{i}=1$ and we shall try to maximize $S=\sum_{i\sim j}z_{i}z_{j}$ . Let $k\nsim l$ . Assume that $\sum_{j\sim k}z_{j}=x$ and $\sum_{j\sim l}z_{j}=y$ . WLOG assume $x\geq y$ . Observe that $S=xz_{k}+yz_{l}+R$ where $R$ is the sum over edges not incident on $k$ or $l$ . Note that $z_{k}x+z_{l}y\leq(z_{k}+\epsilon)x+(z_{l}-\epsilon)y$ . Thus if $z=(z_{1},\ldots,z_{n})$ is a configuration of weights, then for the configuration $z^{\prime}=(z_{1},\ldots,z_{k}+z_{l},\ldots,0,\ldots,z_{n})$ , we obtain $S^{\prime}=x(z_{k}+z_{l})+R>S$ . Thus, by transferring weight from $z_{l}$ to $z_{k}$ , we increase $S$ . If we repeat the procedure again, we see that it stops when the weights are concentrated on two adjacent vertices. This is because whenever the weights are concentrated on at least three vertices, there are two vertices which are not neighbours as the induced subgraph is not complete. If the two adjacent vertices are $i, j$ then $S=z_{i}z_{j}\leq 1/4.$

Let $z_{i}=n^{-1}$ for all $i\in[n]$ . Then the corresponding $S=n^{-2}|E|$ and this is at most $1/4$ by the above argument. Hence the theorem is proved. ∎

Theorem 5.7 (Turan, 1941).

If a simple graph on $n$ vertices has no complete subgraph $K_{p}$ , then $|E|\leq M(n,p):=\frac{(p-2)n^{2}-r(p-1-r)}{2(p-1)}$ where $r\equiv n(\mod p-1)$ .

Note that for $p=3$ the above bound gives Mantel’s theorem bound when $r=0$ and improves it to $(n^{2}-1)/4$ if $r=1$ .

The above bound can be achieved as follows : Let $S_{1},\ldots,S_{p-1}$ be an almost equal partition of $V$ i.e., $S_{1},\ldots,S_{r}$ are subsets of size $t+1$ and the remaining $p-1-r$ subsets are of size $t$ where $n=t(p-1)+r$ with $0\leq r<p-1$ . Construct the complete multi-partite graph on $S_{1},\ldots,S_{p-1}$ such that all the edges between $S_{i}$ and $S_{j}$ are present for $i\neq j$ and these are the only edges. This does not have a complete subgraph $K_{p}$ and twice number of edges is

r(t+1)(n-t-1)+(p-1-r)t(n-t)=r(n-t)-r(t+1)+(p-1)t(n-t)=n(n-t)-r(t+1).

Now substituting $t=\frac{n-r}{p-1}$ gives $M(n,p)$ . This also shows that the bound in Mantel theorem is tight. The uniqueness of the above example as well as other extensions of Turan’s theorem can be found in [Sudakov 2019, Section 13.1].

We will give a proof by induction on $t$ . The original proof by induction on $n$ can be found in [Jukna 2011, Section 4.4]. Also a probabilistic proof can be found in [Jukna 2011, Section 18.4]. See also [Aigner et al. 2010, Chapter 36] for more proofs of Turan’s theorem.

Proof.

Let $t$ be such that $n=t(p-1)+r$ . We will prove by induction on $t$ . If $t=0$ , then $n=r,M(n,p)=n(n-1)/2$ and the theorem trivially holds as $n\leq p-1$ . Now, consider a graph $G$ on $n$ vertices with no $K_{p}$ subgraph (i.e., a subgraph isomorphic to $K_{p}$ ) and let $G$ have the maximum number of edges subject to these constraints. Hence, $G$ contains a subgraph $H$ isomorphic to $K_{p-1}$ . If not, one can add an edge to $G$ without creating a $K_{p}$ subgraph and so contradicting its maximality. The vertices $V-H$ are joined to at most $p-2$ vertices in $H$ . Since $|V-H|=n-p+1=(t-1)(p-1)+r$ and the induced subgraph $\langle V-H\rangle$ also does not contain a $K_{p}$ subgraph, by induction hypothesis, $|E(\langle V-H\rangle)|\leq M(n-p+1,p)$ . Thus, we have that

|E(G)|\leq M(n-p+1,p)+(n-p+1)(p-2)+\binom{p-1}{2}

and one can easily verify that the RHS is equal to $M(n,p)$ . ∎

Exercise* 5.8.

If you generalize the argument for Mantel’s theorem given in the class, what is the bound you get in Turan’s theorem ?

Theorem 5.9.

If a graph $G$ on $n$ vertices has more than $\frac{1}{2}n\sqrt{n-1}$ edges, then $G$ has girth $\leq 4$ . That is $G$ contains a triangle or quadrilateral.

Proof.

Suppose $g(G)\geq 5$ . Let $v_{1},\ldots,v_{d}$ be the neighbours of a vertex $v$ . Since there are no triangles, $v_{j}\notin N_{v_{i}}$ for $i\neq j$ and since there are no quadrilaterals, $N_{v_{i}}\cap N_{v_{j}}=\{v\}$ for $i\neq j$ . Thus, we have that $\cup_{i=1}^{d}N_{v_{i}}\setminus\{v\}\sqcup N_{v}\sqcup\{v\}\subset[n]$ and so $\sum_{i=1}^{d}(d_{v_{i}}-1)+d+1\leq n$ and hence $\sum_{w\sim v}d_{w}\leq n-1$ . Thus, we get

n(n-1)\geq\sum_{v}\sum_{w\sim v}d_{w}=\sum_{w}d_{w}^{2}\geq n^{-1}(\sum_{v}d_{% v})^{2}=n^{-1}4|E|^{2},

where the second equality is because each $d_{w}$ is summed $d_{w}$ many times i.e., for every $v\sim w$ . ∎