Potpun graf

Primjer potpunog grafa s 5 vrhova

Potpun graf je jednostavan graf u kojem je svaki par vrhova spojen bridom.

U potpunom grafu vrijedi:

• $(\mathrm{\forall }u,v\in V)(u\ne v⟹(u,v)\in E)$

• Tada je broj bridova u potpunom grafu $\frac{n(n-1)}{2}$

Suprotno od potpunog grafa je prazan graf u kojem ni jedan vrh nije spojen ni s jednim drugim vrhom u grafu.

Potpun bipartitan graf - Jednostavan bipartitan graf s biparticijom (X, Y ) u kojima je svaki vrh iz X spojen sa svakim vrhom iz Y.