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.
Articles by others on the same topic
There are currently no matching articles.