Zarankiewicz's Lemma
Zarankiewicz's lemma is a result in graph theory about graphs that don't have a complete -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 -subgraph.
We say that a graph has a complete -subgraph if there exist -vertices such that any two of these are connected.
We'll also denote by the set of vertices adjacent to .
Also .
Statement of the Lemma
If is a graph with vertices and does not have a complete -subgraph, then there exists a vertex having degree at most .
Proof
We start by assuming the contrary: every vertex in has degree greater than .
Now we can pick an arbitrary vertex . Because of our assumption, we have so there exists a vertex such that .
Note that , which implies there exists a such that .
By the same argument, we have .
We can keep on repeating this argument to get So we can choose a .
Note that form a complete -subgraph of , which is a contradiction!
So all the vertices in can't have degree greater than , and there has to exist a vertex with degree at most .