Theorem on friends and strangers

From Wikipedia, the free encyclopedia

All the 78 possible friends-strangers graphs with 6 nodes. For each graph the red/blue nodes shows a sample triplet of mutual friends/strangers.

The friendship theorem is a mathematical theorem in an area of mathematics called Ramsey theory.

1 Statement
2 Conversion to a graph-theoretic setting
3 Proof
4 Ramsey's paper
5 Boundaries to the friendship theorem
6 References
7 External link

[edit] Statement

Suppose we had a party of six people. Consider any two of them. They might be meeting for the first time — in which case we will call them mutual strangers; or it might happen that they have met before — in which case we will call them mutual acquaintances. Now the friendship theorem says:

In any party of six people either at least three of them are mutual strangers or at least three of them are mutual acquaintances.

[edit] Conversion to a graph-theoretic setting

A proof of the friendship theorem requires nothing but a three-step logic. In order to help the understanding, it is convenient to convert the problem to a graph-theoretic setting.

Suppose you had a graph with 6 vertices and every pair of points was joined by an edge. Such a graph is called a complete graph, the completeness standing for the fact that there cannot be any more possible edges. A complete graph on n vertices is denoted by the symbol $K n$ .

Now take a $K 6$ . It has 15 edges in all. Let the 6 vertices stand for the six people in our party. Let the edges be coloured red or green depending upon whether the two people represented by the vertices connected by the edge are mutual strangers or mutual acquaintances, respectively. The Friendship Theorem now asserts:

In whatever way you may colour the 15 edges of a $K 6$ red and green, you can never avoid either a red triangle -- that is, a triangle all of whose three sides are red, representing three pairs of mutual strangers -- or, in the alternative, a green triangle, representing three pairs of mutual acquaintances.

[edit] Proof

Focus your attention on any one vertex. Call it P. There are five lines going forth from P. They are coloured red or green — some red, some green. The pigeonhole principle says that at least three of them must be of the same colour; for if there are less than three which are of one colour, say red, then there are at least three which are green!

Let A, B, C be the other ends of these three lines, all of the same colour, say green. If any one of AB, BC, CA is green, then that line with the two edges meeting it at its ends would give a green triangle. If none of AB, BC, CA is green, then all three are red and we have a red triangle, namely, ABC.

[edit] Ramsey's paper

The utter simplicity of this logic which so powerfully produces a very interesting conclusion almost from nowhere, is what makes the friendship theorem interesting. In 1930, in a paper entitled 'On a Problem in Formal Logic,' Frank P. Ramsey proved a very general theorem (now known as Ramsey's theorem) of which the friendship theorem is a meek corollary. It is this theorem of Ramsey which lies at the foundation of the modern theory known as Ramsey theory in combinatorics.

[edit] Boundaries to the friendship theorem

The theorem is not true if you take a party of less than six people. Even if you had five people, the complete graph on 5 vertices in which all the five bounding edges are of one colour and the other five edges are of the other colour will not give a single coloured triangle. Thus 6 has the property that it is the smallest number for which the friendship theorem can be asserted. This fact is symbolically expressed, in Ramsey Theory, by

$N (3,3:2) = 6.$