3
$\begingroup$

I'm working with a first-year professor for a Discrete Mathematics course at my university, and we're trying to come up with a proof for the friendship theorem that's simple enough to show and explain to a group of students just a few weeks into graph theory lectures. We believe it's possible to find one, we just haven't had any luck by ourselves and the ones online all appear to be a bit too complex. Does anyone here have a simple proof or can outline how we could approach finding one?

Thanks!

$\endgroup$
  • $\begingroup$ Welcome to math.SE! Perhaps, giving an example of a couple of approaches that you deem too complicated might save time and help readers give you useful answers. $\endgroup$ – user228113 Feb 26 '16 at 23:09
  • $\begingroup$ For the reader who is casually glancing past, the Friendship Theorem can be stated as "Any two members of a certain College have a unique common enemy who is also a member of the College. Show that there is some College member (the ‘Junior Bursar’) who is everyone else’s enemy." $\endgroup$ – Patrick Stevens Feb 26 '16 at 23:10
5
$\begingroup$

I suppose you have already examined the proof in Proofs from THE BOOK by Martin Aigner and Günter M. Ziegler (Chapter 29 in the first edition, Chapter 39 in the fourth edition) and are looking for something a little different.

The Wikipedia article "Friendship graph" cites a paper by Craig Huneke, The friendship theorem, Amer. Math. Monthly 109 (February 2002), 192-194, in which the author presents not one but two simple proofs of the so-called friendship theorem. In an added note (Amer. Math. Monthly 110 (January 2003), 79) Huneke acknowledges that the first of his two proofs was published earlier by Judith Q. Longyear and T. D. Parsons, The friendship theorem, Nederl. Akad. Wetensch. Proc. Ser. A 75 = Indag. Math. 34 (1972), 257-262.

You can find several proofs (including a version of the Longyear–Parsons proof) online in "A Survey on The Friendship Theorem" by Debashis Chatterjee.

$\endgroup$
  • $\begingroup$ The first proof by Huneke is almost exactly what we were looking for! Thank you! $\endgroup$ – Blawdfire Feb 29 '16 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.