User:Des04/sandbox

Friendship Theorem

The Friendship Theorem, also known as the friendship graph was created by Vera Sos, Paul Erdõs and Alfréd Rényi in 1966. This theorem uses both Combinatorics and algebraic methods.

Theorem

If G is a finite graph in which any two distinct vertices have exactly one common neighbor, then G has a vertex joined to all others. [1] One way in which this theorem may be described for a better understanding is suppose that there are two people at a party who share a common friend. This means that there is one person who is everyone's friend.

Proof

The proof given by Craig Huneke provides the best explanation. [2]

"Suppose there is a vertex of degree k >1. We claim that all vertices hace degree k, unless there is a universal friend. Let A be the set of all vertices of degree k, let B be the set of all vertices of degree different from k, and assume that B is nonempty. By the first claim, every vertex in A is adjacent to every vertex in B. If A or B is a singleton, then that singleton is a universal friend; otherwise there are two different vertices in A, and they have two common neighbors in B, contradicting the hypothesis. It follows that G is k-regular. Next we claim that the number n of vertices in G is exactly k(k-1)+1. This follows by counting the paths of length two in G: by assumption there are ${\tbinom {n}{2}}$ such paths. For each vertex v, there are exactly ${\tbinom {k}{2}}$ paths of length two having v in the middle, giving n * ${\tbinom {k}{2}}$ total paths of length two. Equating both counts permits us to conclude that n=k(k-1)+1. We can assume that k≥3, else n=3 and the theorem is clear."

Friendship Graph

An example of the friendship graph can be seen here

More on Friendship graphs can be seen here

References

• Huneke, Craig. "The Friendship Theorem." The American Mathematical Monthly 109.2 (2002): 192-94. JSTOR. Mathematical Association of America. Web. <http://www.jstor.org/discover/10.2307/2695332?uid=3739832&uid=2129&uid=2&uid=70&uid=4&uid=3739256&sid=21102213900737>.
• Mertzios, George B., and Walter Unger. "The Friendship Problem on Graphs." ROGICS'08, 17 May 2008. Web. <http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf>.