No campo da matemática da teoria dos grafos, um grafo bipartido completo ou biclique é um tipo especial de grafo bipartido onde cada vértice do primeiro conjunto está associado a cada vértice do segundo conjunto.
Um grafo bipartido completo, G:= (V1 + V2, E), é um grafo bipartido tal que para quaisquer dois vértices, v1 ∈ V1 e v2 ∈ V2, v1v2 é uma aresta em G. O grafo bipartido completo com partições de tamanho |V1|=m e |V2|=n, é denotado Km,n.
Os grafos estrela S3, S4, S5 e S6.O grafo de utilidade K3,3
Para qualquer k, K1,k é chamado uma estrela. Todos os grafos bipartidos completos que são árvores são estrelas.
O grafo K1,3 é chamado uma garra, e é usado para definir os grafos sem garra.
O grafo K3,3 é chamado de grafo de utilidade. Esta prática vem de um quebra-cabeça matemático tradicional, no qual três utilidades devem ser ligadas a cada três edifícios; é impossível de resolver sem cruzamentos, devido à não-planaridade de K3,3.
Dado um grafo bipartido completo, ele possui dois autovalores simétricos (o índice e o seu simétrico) e os demais nulos.[1]
Dado um grafo bipartido, encontrar o seu subgrafo bipartido completo Km,n com o número máximo de arestas mn é um problema NP-completo.
Um grafo planar não pode conter K3,3 como um menor; um grafo periplanar não pode conter K3,2 como um menor (Estas não são condições suficientes de planaridade e planaridade exterior, mas necessárias).
Um grafo bipartido completo Kn,n é um grafo de Moore e uma (n,4)-gaiola.
Um grafo bipartido completo Kn,n ou Kn,n+1 é um grafo de Turán.
