Four-step path lemma for a dense bipartite graph

ID: four-step-path-lemma-for-a-dense-bipartite-graph

Let a bipartite graph have vertices in each class and at least edges. There is a subset of one class with such that every pair of its vertices has at least four-edge walks between them. Declare a pair of left vertices bad if it has fewer than common neighbours, with . For a random right vertex , put and let count ordered bad pairs inside . Then and . Some has , so and . Remove vertices with more than bad partners. At least half remain. For any two remaining vertices, at least middle vertices are good partners of both. Each supplies at least walks, giving the bound.

New to topics? Read the docs here!