Grafo colorato

Anér · Messaggio da **Anér** » 13 gen 2009, 21:05

Si prenda un grafo di $ \binom{2n}{n} $ vertici, tale che ogni coppia di vertici sia collegata, e si colorino tutti i lati di rosso o di blu. Dimostrare che esiste un sottoinsieme di $ n+1 $ vertici collegati tutti in rosso o tutti in blu.

kn · Messaggio da kn » 14 gen 2009, 18:21

Dimostrare che esiste un sottoinsieme di n+1 vertici collegati ...

Ho capito male o i vertici sono tutti collegati tra loro?

Anér · Messaggio da **Anér** » 15 gen 2009, 20:37

Sì, ogni coppia di vertici è unita da un lato.