THE FRIENDSHIP THEOREM AND THE LOVE PROBLEM
J. M. Hammersley · Cambridge University Press eBooks · 1983
“The nymph Echo fell in love with Narcissus, but was repulsed. Aphrodite punished him for his cruelty by making him enamoured of his own image in a fountain. His fruitless attempts to approach this beautiful object led to his despair and death. He was changed into the flower that bears his name.” — Sir Paul Harvey, Oxford Companion to Classical Literature . Community relations In response to the editor's request for a survey article on a combinatorial topic, I have assembled under a single heading —the love problem, as I shall call it — material that has previously appeared in separate contexts and diverse guises, such as the solubility of Diophantine quadratic matrix equations, the construction of block designs, the existence of finite geometries, etc. However, I shall only mention a handful of references as leads into the extensive literature, which I could not hope to cover by anything approaching a complete bibliography. Moreover, in stressing the graph-theoretic aspects of the matter, I shall be adopting a rather different line from traditional treatments. Let us begin with a special case of the love problem, known as the friendship theorem. I do not know who first stated this theorem: the earliest published paper that I have come across is Wilf (1971), who cites an earlier unpublished account by Graham Higman in 1968.