Ein Graph ${\displaystyle {}G=(V,E)}$ heißt bipartit, wenn es eine disjunkte Zerlegung

${\displaystyle {}V=A\uplus B\,}$

derart gibt, dass es nur Kanten zwischen ${\displaystyle {}A}$ und ${\displaystyle {}B}$ gibt.