Faci o parcurgere în lățime plecând din nodul 1 ( de exemplu ) si marchezi fiecare vecin al nodului curent cu un anumit număr, dar diferit de nodul tată. Să presupunem că reții un vetor v, de lungime n și îi asociezi fiecărui nod un numar, care poate fi 1 sau -1. Dacă nodul curent are valoarea 1, atunci vecinii săi vor primi valoarea -1, iar daca nodul curent are valoarea -1, vecinii săi vor primi 1. La final, verifici dacă v[i] = v[j], oricare ar fi i si j cuprinși între 1 și n și daca există muchie în graf de la i la j. v[i] = v[j] înseamnă că i și j sunt în aceeași submulțime, dar există și muchie între ele, ceea ce ar contrazice definiția unui grad bipartit. Pentru ca un graf să fie bipartit, el trebuie să poată fi partiționat în două submulțimi,astfel încât orice muchie din graf să aibă un vârf într-o submulțime și celălalt vârf în a doua submulțime.
O posibilă implementare :
