Grafo bipartito completo

Un grafo bipartito completo ${\displaystyle G:=(V_{1}\cup V_{2},E)\,}$ es un grafo bipartito tal que ${\displaystyle \forall v_{1}\in V_{1},\forall \ v_{2}\in V_{2}\Rightarrow e(v_{1},v_{2})\in E.\,}$ Es decir, un grafo bipartito completo está formado por dos conjuntos disjuntos de vértices y todas las posibles aristas que unen esos vértices.[1]

El grafo completo bipartito con particiones de tamaño ${\displaystyle \left|V_{1}\right|=m}$ y ${\displaystyle \left|V_{2}\right|=n,}$ es denotado como ${\displaystyle K_{m,n}\,}$.[1]

• 
  K_3,1 (grafo estrella S₃)
• 
  K_3,2
• 
  K_3,3

Sea ${\displaystyle K_{m,n}\,}$ un grafo bipartito con ${\displaystyle \left|V_{1}\right|=m}$ y ${\displaystyle \left|V_{2}\right|=n}$, se verifica:^{[cita requerida]}

• ${\displaystyle \left|E\right|=\left|V_{1}\right|\cdot \left|V_{2}\right|=m\cdot n}$
• ${\displaystyle K_{m,n}\,}$ posee ${\displaystyle m^{n-1}\cdot n^{m-1}}$ árboles de expansión.

• Grafo bipartito
• Grafo completo

• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053.