7. Semplici Tavole Rotonde

[aetwaf]

$2n$ persone si incontrano a un convegno

Ognuno di essi conosce al minimo $n$ persone

Dimostrare che si possono prendere $4$ persone e farli sedere attorno a un tavolo in modo che ognuno conosca i suoi $2$ vicini

[lucaboss98]

Immagino le [tex]2n[/tex] persone come vertici di un grafo, e da ogni vertice partono almeno [tex]n[/tex] corde. Devo dimostrare che esistono [tex]4[/tex] vertici tali che formano un quadrilatero chiuso.
Dal vertice A partono (almeno) [tex]n[/tex] corde, una corda arriva in B , da cui partono (almeno) altre [tex]n-1[/tex] corde, prendiamo un vertice C da cui arriva una di queste.
Ora divido in due casi: Esiste un C tale che A e C non sono collegate, allora (per pigeonhole) le corde da A (che non vanno in B) sono almeno [tex]n-1[/tex] , analogamente quelle da C, visto che i vertici (non vanno considerati A,B,C) sono [tex]2n-3[/tex] e le corde almeno [tex]2n-2[/tex] esiste un vertice D collegato sia ad A che a C, e quindi la tesi.
Non esiste un C tale che A e C non sono collegate, ma allora basta prendere due di questi punti (diciamo C e D) che sono collegati sia ad A che a B, e quindi la tesi è verificata.
Questo presuppone che A sia collegato ad almeno [tex]3[/tex] , quindi devo vedere quando [tex]2n=4[/tex].
Allora ogni punto è collegato ad almeno altri due, e visto che la scelta dei [tex]4[/tex] è obbligata, ho la tesi.
Spero di non aver fatto sviste.

[aetwaf]

Mi sembra corretta