Vegyes feladatok: VF_000002
(Feladat azonosítója: VF_000002 )
Témakör: *Kombinatorika (gráfelmélet, Ramsey-tétel R(3,3))

Bizonyítsuk be, hogy hattagú társaságnak mindig van vagy három olyan tagja, akik kölcsönösen ismerik egymást, vagy három olyan, akik kölcsönösen nem ismerik egymást.



 

Tekintsük a társaság egyik tagját, $A$ urat. Ha ez kettőnél többet ismer és ezek közül kettő ismeri egymást, akkor már van három egymást kölcsönösen ismerő tag; ha pedig egyik sem ismeri a másikat, a második eset következik be. Ha $A$ úr ismerőseinek száma nem haladja meg a kettőt, vagyis az előtte ismeretlenek száma legalább három, akkor ez utóbbiak vagy mind ismerik egymást, (1. eset) vagy van köztük legalább kettő, akik nem ismerik egymást. Minthogy ezek $A$ úr előtt is ismeretlenek, a társaságnak megint van 3, kölcsönösen ismeretlen tagja.