---
tag: S567EY6SA2
kind: proof
name: Proof of the theorem on friends and strangers
msc: [05C55, 05D10]
proves: 0NYM0ZGAK9
uses: [03WKB2H474, 0HGVCWQGY3]
methods: [0WCP0PVET6]
sources:
  - url: https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers
    locator: Proof
---

## Proof

We look at the edges at one vertex and use the pigeonhole principle.

1. Colour each edge of the [[complete graph|03WKB2H474]] $K_6$ red or blue. Fix a vertex $v$.
2. The vertex $v$ is adjacent to the other $5$ vertices, so it lies on $5$ edges.
3. Suppose that at most $2$ of these edges were red and at most $2$ were blue. Then there would be at most $4$ edges, a contradiction. This is the [[pigeonhole principle|0HGVCWQGY3]] for $5$ edges and $2$ colours.
4. So at least $3$ of these edges have one colour. By symmetry of the two colours, we may call this colour blue.
5. Let $a, b, c$ be three distinct vertices such that $va$, $vb$ and $vc$ are blue.
6. Case 1: one of the edges $ab$, $bc$, $ca$ is blue, say $ab$. Then the edges $va$, $vb$ and $ab$ between $v, a, b$ are all blue.
7. Case 2: none of $ab$, $bc$, $ca$ is blue. Then all three are red, and the three edges between $a, b, c$ are all red.
8. In both cases there are three vertices such that the three edges between them have the same colour.

## Idea

Some vertex sees three others along edges of the same colour, say blue. Among these three, a single blue edge closes a blue triangle with the vertex. If there is no blue edge among them, they form a red triangle.