Graphe biparti et chaînes impaires

Théorie des graphes · Puissances et comptage des chemins · niveau 2

Énoncé

Un graphe est biparti si l'on peut colorier ses sommets en deux couleurs sans qu'aucune arête relie deux sommets de même couleur. Montrer qu'un graphe biparti n'a aucune chaîne de longueur impaire d'un sommet vers lui-même. Que vaut alors $(A^{2 k + 1})_{ii}$ ?

Corrigé

Colorions les sommets en noir et blanc comme le permet l'hypothèse. Chaque arête change la couleur : c'est exactement la définition.

Une chaîne de longueur $ℓ$ partant de $i$ franchit $ℓ$ arêtes, donc change $ℓ$ fois de couleur. Si elle revient en $i$ , elle doit retrouver la couleur de départ : le nombre de changements est donc pair. Ainsi $ℓ$ est pair, et aucune chaîne fermée de longueur impaire n'existe.

Par conséquent, pour tout sommet $i$ et tout $k \geq 0$ :

$(A^{2 k + 1})_{ii} = 0.$

Autrement dit, toutes les puissances impaires de $A$ ont une diagonale nulle.

La réciproque est vraie aussi (un graphe sans cycle de longueur impaire est biparti), ce qui donne un critère : biparti $⟺$ aucune diagonale non nulle en puissance impaire.

Énoncé

Corrigé

Exercices semblables