http://www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml

A famous theorem in combinatorics known as the Friendship Theorem states the following:

“In a party of six people, there are at least three mutual acquaintances, or there are at least three mutual strangers.”

It is clear that this statement is equivalent to saying that if we use a bicoloring of the edges in the complete graph on 6 vertices, where a red edge is drawn between a pair of acquaintances and a blue edge is drawn otherwise (where nodes represent people), then there exists at least one monochromatic triangle. 

The proof of this claim is a simple application of the Pigeonhole Principle.  Consider any vertex in K_6, call it x.  Clearly x has degree 5 and thus is incident with at least three edges of the same color (by Pigeonhole Principle), WLOG say red.  Let a, b, and c be 3 vertices connected to x by a red edge.  If any of the edges between a, b, or c is red, then there will be a monochromatic red triangle.  (If there is a red edge between a and b, then triangle xab will be a red triangle.)

If none of the edges between a, b, or c is red then clearly triangle abc  will be a monochromatic blue triangle.

In either case, we have shown that there will be a monochromatic triangle, which completes the proof.

In fact, A.W. Goodman has shown that any bicoloring of the edges in K_6 must have at least 2 monochromatic triangles.  His theorem gives the greatest lower bound on the number of monochromatic triangles that must appear in any bicoloring of the edges of K_n.  The bounds and the proof of the bounds is given here:  http://www.artofproblemsolving.com/Forum/viewtopic.php?t=5820

These theorems relate to what we have discussed in class because we are using graph theory to analyze social networks.    This topic is related to Ramsey Theory, which is a popular topic in graph theory/ combinatorics that further generalizes the the Friendship Theorem so that it may be applied to some larger social networks.