The Friendship Problem on Graphs
George B. Mertzios and Walter Unger
In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes occupies l ≥ 2 common neighbors. We prove that every graph, which satisfies this generalized l-friendship condition, is a regular graph.
Keywords: Friendship theorem, friendship graph, windmill graph, Kotzig’s conjecture.