Grafos bipartidos

Um grafo G diz-se bipartido de tipo (p,q) se fôr um grafo simples de ordem p+q e existir uma partição do conjunto de todos os vértices em dois subconjuntos V1 e V2, com p e q elementos respectivamente, tal que nenhuma aresta de G tenha ambas as extremidades em V1 nem ambas as extremidades em V2.
Se além disso se para todo o par de vértices v1 em V1 e v2 em V2 o grafo G contiver a aresta {v1,v2} então dizemos que G é um grafo bipartido completo de tipo (p,q).

Designa-se por Kp,qo grafo bipartido completo de tipo (p,q) .


Veja mais alguns exemplos.