Kompletný a bipartitný graf

Jednoduchý graf, ktorý obsahuje všetky možné hrany (teda má hranu medzi každou dvojicou vrcholov) voláme kompletný graf. Kompletný graf o $N$ vrcholoch sa zvykne označovať $K_N$.

Hovoríme, že graf je bipartitný, ak sa jeho vrcholy dajú rozdeliť na dve časti tak, že medzi žiadnymi dvoma vrcholmi z rovnakej časti nevedie hrana. Týmto dvom častiam hovoríme partície grafu. Príkladom použitia bipartitného grafu je napríklad tanečný večierok: graf, v ktorom vrcholy reprezentujú ľudí a hrany spájajú dvojice, ktoré spolu chcú tancovať, bude pravdepodobne bipartitný -- jednu partíciu budú tvoriť chlapci a druhú dievčatá.

Bipartitný graf sa niekedy definuje aj ako graf, ktorý neobsahuje cykly nepárnej dĺžky. Dá sa ukázať, že táto definícia je ekvivalentná s tou predošlou. Je zaujímavé, že napriek tomu v Slovenčine existuje slovné spojenie ''ľúbostný trojuholník''.