De ce contează?
La un turneu vrei să împarți elevii în două echipe, roșie și albastră, astfel încât fiecare meci programat să fie între un roșu și un albastru — niciodată doi colegi de echipă unul împotriva celuilalt. Uneori reușești perfect; alteori, oricum ai împărți, rămâne mereu un meci „interzis" între doi din aceeași echipă. Un graf în care reușești împărțirea curată se numește bipartit.
Intuiția
Imaginează nodurile ca jucători și muchiile ca meciuri. Un graf e bipartit dacă poți colora nodurile cu două culori astfel încât fiecare muchie să lege culori diferite. Echivalent: poți împărți nodurile în două mulțimi, iar toate muchiile trec dintr-o mulțime în cealaltă, niciuna în interiorul aceleiași mulțimi. Întrebarea „e bipartit?" devine astfel: „pot colora harta cu doar 2 culori fără ca doi vecini să primească aceeași culoare?".
Trei formulări, aceeași proprietate: graful e bipartit ⇔ nodurile se pot colora cu 2 culori fără nicio muchie între culori egale ⇔ graful nu conține niciun ciclu de lungime impară. Un singur ciclu impar, oriunde în graf, strică totul.