Graf yang simpul-simpulnya dapat dibagi menjadi dua himpunan saling lepas sedemikian sehingga tidak ada sisi di antara dua simpul dalam himpunan yang sama.