Probleme de graphe

[robin]

Bonjour,

Dans une communauté d'au moins six personnes, tous les membres échangent des lettres avec exactement trois autres membres. Montrer que la communauté peut être divisée en deux sous-groupes (non vides) tels que chaque membre échange des lettres avec au moins deux personnes du groupe auquel il appartient.

bonne chance

[Flodelarab]

c marrant, je suis pas d'accord avec le truc a démontrer...

prenons un groupe de 6 personnes (le minimum).
Pour que la propriété soit vraie, chaque sous groupe doit contenir au moins 3 personnes. On a donc une répartition 3/3.

Les 3 doivent former un triangle....
or il est facile de voir qu'avec 6 points d'ou partent 3 segments chacun, on peut trouver un cas qui ne forme aucun triangle ....

contre exemple => propriété fausse

[musichien]

ah oui, tiens, c'est vrai! Sur MSN, j'ai fait une démo pour 6, puis on conclut par récurrence, mais je suis allé un peu trop vite en besogne. Considérons un sommet, et les 3 sommets auxquels il est relié. Alors, ces 3 sommets peuvent trés bien être reliés chacun aux 2 autres qui restent, et cela ne forme aucun triangle. En revanche, pour toute autre configuration, ça marche forcément.