graphe biparti

COMBINATOIRE

Graphe non orienté dont l’ensemble des sommets s’écrit comme une réunion disjointe de deux ensembles de sommets stables.
Ce sont des graphes que l’on peut colorer en utilisant au plus deux couleurs.
Le théorème suivant a été établi par Denes König en 1916 : un graphe est biparti si et seulement s’il ne contient pas de cycles de longueur impaire.