Zarankiewicz's Lemma

Zarankiewicz's lemma is a result in graph theory about graphs that don't have a complete $k$-subgraph. It is attributed to Kazimierz Zarankiewicz (1902-1959).

Before we can begin to understand Zarankiewicz's lemma, we need to get a few definitions straight. I assume you are familiar with the basic graph theoretical ideas like vertices, degrees, and edges. We start by giving the definition of a complete $k$-subgraph.

We say that a graph has a complete $k$-subgraph if there exist $k$-vertices such that any two of these are connected. $_\square$

We'll also denote by $C(V)$ the set of vertices adjacent to $V$.

Also $\displaystyle \bigcap_{i=1}^n A_i=A_1\cap A_2 \cap A_3 \cdots \cap A_n$.

If $G$ is a graph with $n$ vertices and does not have a complete $k$-subgraph, then there exists a vertex having degree at most $\left \lfloor \dfrac{(k-2)n}{k-1} \right\rfloor$. $_\square$

We start by assuming the contrary: every vertex in $G$ has degree greater than $\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor$.

Now we can pick an arbitrary vertex $V_1$. Because of our assumption, we have $|C(V_1)|>\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor,$ so there exists a vertex $V_2$ such that $V_2 \in C(V_1)$.

Note that $|C(V_1)\cap C(V_2)|=|C(V_1)|+|C(V_2)|-|C(V_1)\cup C(V_2)| \geq 2\left(1+\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor\right)-n>0$, which implies there exists a $V_3$ such that $V_3 \in C(V_1)\cap C(V_2)$.

By the same argument, we have $|C(V_1)\cap C(V_2)\cap C(V_3)|\geq 3\left(1+\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor\right)-2n>0$.

We can keep on repeating this argument to get $\left|\displaystyle\bigcap_{i=1}^{k-1} C(V_i)\right|\geq (k-1)\left(1+\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor\right)-(k-2)n>0.$ So we can choose a $V_k\in \displaystyle\bigcap_{i=1}^{k-1} C(V_i)$.

Note that $V_1, V_2, V_3, \ldots , V_k$ form a complete $k$-subgraph of $G$, which is a contradiction!

So all the vertices in $G$ can't have degree greater than $\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor$, and there has to exist a vertex with degree at most $\left\lfloor \dfrac{(k-2)n}{k-1}\right\rfloor$. $_\square$

$1$. Graph Theory

$2$. Contradiction

$3$. PIE