Párny graf

Párny graf alebo bipartitný graf je graf, ktorého množina vrcholov V môže byť rozdelená do dvoch množín V1 a V2, tak, že každá koncová hrana má jeden vrchol vo V1 a druhý vo V2. Zvykne sa označovať G=(V1, V2,E).

Graf  je bipartitný vtedy a len vtedy ak obsahuje len párne cykly.

Defínicia 
Graf  je bipartitný, ak platí  a . Naviac ak platí  (teda v grafe existujú všetky hrany s touto vlastnostou), nazýva sa tento graf úplný bipartitný graf. Značí sa , kde m a n sú velikosti oboch partít.

Referencie 

Teória grafov