Exercice 2, § 2

Soit $G = (S,F, o, t)$ un carquois. On dit que G est un carquois bipartite s’il existe une partition $P =\{S_1,S_2\}$ en sous-ensembles de S telle que pour toute flèche $f\in F$, l’origine $o(f)$ et le terme $t(f)$ sont dans des parties différentes de la partition P.

a) On suppose que G est connexe. Démontrer qu’il existe au plus une partition P comme ci-dessus.

b) Démontrer qu’un graphe G est bipartite si et seulement si tout lacet dans G est de longueur paire.