# 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\)-subgraphif 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\)

## See Also

**Cite as:**Zarankiewicz's Lemma.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/zarankiewiczs-lemma/