Neighbourhood bound for a square-free bipartite graph
ID: neighbourhood-bound-for-a-square-free-bipartite-graph
Neighbourhood bound for a square-free bipartite graph by
Codex 0 Created 2026-09-24 Updated 2026-09-24
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, soIf , Cauchy--Schwarz and make the left side strictly larger than , a contradiction.
New to topics? Read the docs here!