Théorème de Konig

[jeremux]

Le théorème de Konig dit qu'un graphe est biparti s'il il n'y a pas de cycle de longueur impair.

Quelqu'un aurait-il une démonstration ?

Merci d'avance.

[Doraki]

Prends un sommet au hasard, colorie-le au hasard,
colorie tous ses voisins de la seule façon possible et ainsi de suite.
Montre qu'il ne peut pas y avoir de problème.

S'il reste des sommets, recommence.