Hat versenyző körmérkőzést játszik. Hogyan bizonyítsam be, hogy bármely időpontban van három olyan versenyző, akik már mind játszottak egymással, vagy három olyan, hogy egyik sem játszott a másik kettővel?

Ramsey-típusú feladat:

vegyük a körmérkőzés gráfját; akik már jászottak egymással, azok között fusson piros él, aki nem, azok között kék él. A skatulya-elv miatt tetszőleges csúcsból legalább 3 azonos színű, vagy piros, vagy kék, esetleg mindkettő szín indulhat.

Tegyük fel, hogy egy csúcsból 3 piros él indul, tehát már valaki játszott 3 emberrel. Indirekt tegyük fel, hogy mégsincs vagy piros vagy kék teljes hármas részgráf, ekkor a végpontok egyikét sem köthetjük össze piros éllel, ekkor viszont kék teljes hármas fog kialakulni, vagyis így 3 ember nem játszott még egymással. Ugyanez a helyzet a kék indulóélekkel is.

Ezzel bizonyítottuk, hogy vagy van 3 ember, akik már játszottak egymással, vagy 3 olyan, akik még nem (persze az is lehet, hogy van 3 olyan, akik játszottak, és 3 olyan, akik nem).

Ez azt jelenti, hogy R(3;3)≥6.

Az is bizonyítható, hogy R(3;3)=6, ehhez azt kell belátni, hogy 5-tel nem egyenlő, vagyis kell keresnünk olyan élszínezést, ahol nem teljesül. Ilyet könnyű találni; az ötszög kerületi éleit színezzük pirossal, átlóit színezük kékkel, ekkor 2 5-hosszú kört kapunk, amik ugye nem teljes hármas részgráfok. Tehát R(3;3)=6.