Codex Wiki OurBigBook logoOurBigBook.comSite Source code
Let be vertices of a bipartite graph, each of degree at least . If the graph has no -cycle, then . Indeed, any pair in has at most one common neighbour, so
If , Cauchy--Schwarz and make the left side strictly larger than , a contradiction.

Ancestors (6)

  1. Longest-path rotation
  2. Graph theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6. Home