Sumber: sparkselite.com.au

Jika ada 6 orang bertemu, melakukan pertemuan maka jelas setiap 2 orang dari 6 orang tersebut hanya memiliki 2 kemungkinan hubungan: saling mengenal atau sebaliknya tidak saling mengenal, baru berkenalan pada pertemuan tersebut. Nah.. yang jadi pertanyaan adalah:

Ada berapa orang yang saling mengenal atau sebaliknya tidak saling mengenal?

Pertanyaan diatas dapat dijawab oleh teorema berikut:

Teorema: Jika 6 orang bertemu maka paling tidak ada 3 orang saling mengenal atau sebaliknya paling tidak ada 3 orang tidak saling mengenal

Teorema diatas punya banyak nama ada yang menyebutnya Teorema pada teman dan orang asing (Theorem on friends and strangers), ada yang menyebutnya Teorema pesta (Party Theorem) ,ada yang yang menyebutnya Teorema Ramsey (Ramsey’s Theorem) karena pertama kali di publish oleh Frank P. Ramsey.

Jika 6 orang tersebut direpresentasikan dengan 6 titik, Hubungan saling mengenal dengan garis berwarna biru dan hubungan tidak saling mengenal dengan garis berwarna merah. Itu berarti setiap 2 titik terhubung garis bisa garis merah atau biru. Diperoleh Graph komplit yaitu setiap 2 titik terhubung garis dengan 6 titik dan 15 garis, dinotasikan . Sekarang kita bisa menyatakan teorema diatas menurut Teori Graph:

Bagaimanapun cara mewarnai 15 garis pada   dengan warna merah atau biru maka akan mucul segitiga merah yaitu segitiga yang ke-3 sisinya berwana merah yang merepresentasikan 3 orang tidak saling mengenal atau mucul segitiga biru yang merepresentasikan 3 orang saling mengenal,

Dengan kata lain jika kita mewarnai ke-15 garis pada  dengan warna merah atau biru maka akan selalu terdapat 2 kemungkinan muncul segitiga merah atau segitiga biru.

Bukti: 

Ambil salah satu titik, sebut saja maka terdapat 5 garis yang menghubungkan dengan ke-5 titik lainnya dengan kemungkinan warna merah atau biru. Berdasarkan prinsip sarang merpati (pigeonhole Principle)  ada 3 garis berwarna sama. Tanpa kehilangan keumuman ( Without loss of generality) Sebut saja 3 garis tersebut berwana merah menghubungkan dengan ,  dan . Jika salah satu garis yang antara ,  dan berwarna merah maka akan terbentuk segitiga merah, sebaliknya akan terbentuk segitiga biru

QED