Úplný bipartitní graf Kr,s je bipartitní graf, kde |V1| = r, |V2| = s, a ve kterém je hranou spojen každý z r vrcholů množiny V1 s každým z s vrcholů množiny V2.