OliForum Matematico

Date 9 persone, ognuna delle quali conosce al più 3 lingue, sapendo che in ogni gruppo di 3 persone ce ne sono almeno 2 che parlano la stessa lingua, dimostrare che esistono 3 persone in grado di dialogare in una lingua comune.

E' un po' che non guardo la policy del forum, spero che noi vecchi possiamo ancora rispondere ai post dei ragazzi

Sia la tesi falsa e wlog (a meno di trascurare le lingue parlate da una sola persona) ogni lingua parlata da esattamente 2 persone.
Possiamo quindi un grafo nel quale i vertici rappresentano le persone e gli archi le lingue:
Sia $ G $ un grafo di 9 vertici tale che:
1) i vertici siano di grado al massimo 3
2) comunque scelti 3 vertici c'è un arco tra essi.
Dalla $ [1] $ si ottiene che esistono due vertici non connessi tra di loro.
Siano $ V_1, V_2 $ due vertici non connessi, per la $ [2] $ ogni altro vertice sarà quindi connesso ad almeno uno di essi e la somma dei loro gradi è almeno $ 9-2=7>6 $ ma ciò contraddice la $ [1] $.