Dvodelni graf (tudi bipartitni graf ali bigraf) je v teoriji grafov graf, ki se mu lahko točke razdeli v dve disjunktni množici ${\displaystyle U\,}$ in ${\displaystyle V\,}$ tako, da vsaka povezava povezuje točko iz množice ${\displaystyle U\,}$ s točko v množici ${\displaystyle V\,}$ (tudi obratno velja: vsaka povezava povezuje tudi točko iz ${\displaystyle V\,}$ s točko v ${\displaystyle U\,}$). Tako se dobita dve neodvisni množici. Iz tega sledi, da dvodelni graf ne vsebuje povezave, ki bi povezovala dve točki iste množice. Lahko pa se množico točk razdeli v dve skupini.

Dvodelni graf nima cikle z liho dolžino. Enostavni dvodelni graf se označuje z ${\displaystyle G=(V,E)\,}$ kjer je:

• ${\displaystyle V\,}$ število točk
• ${\displaystyle E\,}$ število povezav

• graf, ki nima lihih ciklov, je dvodelen. Dvodelni graf tako nima klik, ki bi imele velikost 3 ali več.
• ciklični graf s sodim številom točk je dvodelen
• vsak ravninski graf (povezave se ne sekajo), kjer je vsako lice v ravninskem prikazu sestavljeno iz sodega števila povezav, je dvodelen
• graf je dvodelen, če se ga lahko obarva z dvema barvama (kromatično število je manjše ali enako 2)
• najmanjša velikost pokritja točk je enaka velikosti največjega ujemanja
• največja velikost neodvisne množice sešteta z največjim ujemanjem je enaka številu točk
• za povezani dvodelni graf je najmanjša velikost pokritja povezav enaka največji velikosti neodvisnih množic
• za povezani dvodelni graf je velikost najmanjšega pokritja povezav prišteta k velikosti najmanjši pokritosti točk, enaka številu točk
• vsak dvodelni graf je popolni graf
• spekter grafa je simetričen, če in samo če je graf dvodelen.

Zgledi dvodelnih grafov so tudi drevesa, hiperkocke in cikli s sodim številom točk.^[1]

Če se dve množici ${\displaystyle U\,}$ in ${\displaystyle V\,}$ barva z dvema barvama tako, da so vse točke v ${\displaystyle U\,}$ pobarvane z modro barvo in vse točke v ${\displaystyle V\,}$ z zeleno barvo, potem se vsaka točka konča in začne z različno barvo. Pogosto se dvodelni graf označuje z

Dvodelni graf je povezani graf. Njegovo dvodelnost se lahko definira s sodostjo ali lihostjo razdalje od poljubno izbrane točke. Ena podmnožica točk ima to razdaljo sodo, druga podmnožica pa liho.

Dvodelnost grafa se torej ugotavlja tako, da se določi dve podmnožici ${\displaystyle U\,}$ in ${\displaystyle V\,}$ za vsako povezano komponento grafa in potem se za vsako točko posebej ugotovi, če končne točke pripadajo različnim podmnožicam.

• polni dvodelni graf

• Teorija grafov-dvodelni graf (slovensko)
• Weisstein, Eric Wolfgang. »Bipartite Graph«. MathWorld.
• Lekcije iz teorije grafov s simulacijo Arhivirano 2010-05-27 na Wayback Machine. (angleško)
• Dvodelni graf Arhivirano 2012-09-19 na Wayback Machine. na PlanetMath (angleško)
• Razredi grafov Arhivirano 2010-12-06 na Wayback Machine. (angleško)