Definitie:
Fie G =(V, M) un graf neorientat. Graful G se numeşte graf bipartit, dacă există două multimi
nevide Vl şi V2 cu proprietătile:
V1 reunit V2 = V
V1 intersectat V2 = multimea vida
orice muchie a lui G are o extremitate în V1 şi pe cealaltă în V2.
Exemplu de graf neorientat bipartit:
G=(V, M) unde: V={ 1,2,3,4} si M={[1,3], [2,3], [2,4]}
Reprezentarea sa grafică este:
