The friendship problem on graphs.
George B. Mertzios, Walter Unger · RWTH Publications (RWTH Aachen) · 2008
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 ℓ ≥ 2 common neighbors. We prove that every graph, which satisfies this generalized ℓ-friendship condition, is a regular graph. Keywords: Friendship Theorem, friendship graph, windmill graph, Kotzig’s conjecture. 1