Prouver que le 2-colorabilité est en L de Undir-joignabilité est en L

Question

Soit Undir-joignabilité le problème suivant: étant donné un graphe non orienté G et deux sommets spécifiés s et t dans G, est-il un chemin de s à t dans G?

Je dois prouver que le 2-L est en colorabilité, en sachant que Undir-joignabilité appartient à la classe de complexité L.

Je ne sais pas comment commencer.

Answer 1

Astuce:. Un graphique ne bipartites s'il y a une promenade de longueur impaire d'un sommet à lui-même