using the pigeonhole principle to show that $\exists i,j,k.(i<j<k)\wedge(<i,j>,<j,k>,<k,i>\in R) \vee (<i,j>,<j,k>,<k,i>\notin R)$

Question

If $R$ is a symmetric and irreflexive relation $R\subseteq [6]\times [6]$ , $[6]=\{1,....6\}$

How can I show that:

$\exists i,j,k.(i<j<k)\wedge(\langle i,j\rangle,\langle j,k\rangle, \langle k,i\rangle\in R) \vee (\langle i,j\rangle,\langle j,k\rangle,\langle k,i\rangle\notin R)$

How can I use the pigeonhole principle to solve the problem ?

Answer 1

I'm assuming that the relation is irreflexive (no element is related to itself) rather than non-reflexive (it is not the case that each element is related to itself). Such a relation can be modeled with a simple graph. In that case, the statement to be proved is:

Given a simple graph with six vertices, there is either a set of three vertices all of which adjacent to each other, or a set of three vertices none of which are adjacent to each other.

This is sometimes called the Theorem on friends and strangers. The proof is a straightforward (perhaps slightly tedious) case-by-case analysis.