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).
Definitions and Notations
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\).
Statement of the Lemma
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\)
Proof
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\)