Graphe biparti complet

Si m = 1, le graphe complet biparti K_1,n est une étoile et est noté ${\displaystyle S_{n}}$.

Les étoiles S₃, S₄, S₅ et S₆.

En particulier, les étoiles sont des arbres. D'ailleurs, tous les graphes bipartis complets qui sont des arbres sont des étoiles.

Voici des exemples pour m = 3.

• 
  K_3,1
• 
  K_3,2
• 
  K_3,3

Le graphe K_3,3 est le plus petit graphe cubique non planaire. Il sert dans les caractérisation des graphes planaires de Kazimierz Kuratowski et de [[Klaus Wagner|Klaus Wagner]]. C'est lui qui réside derrière l'énigme des trois maisons.

• Le graphe biparti complet ${\displaystyle K_{n,n}}$ est un graphe de Moore et une ${\displaystyle (n,4)}$-cage.
• Les graphes bipartis complets ${\displaystyle K_{n,n}}$ et ${\displaystyle K_{n,n+1}}$ sont des [[Graphe de Turán|graphes de Turán]].
• Le graphe biparti complet ${\displaystyle K_{n,n}}$ est un graphe symétrique : il est arête-transitif, sommet-transitif et arc-transitif.
• Le nombre d'arbres couvrants du graphe biparti complet ${\displaystyle K_{m,n}}$ est ${\displaystyle m^{n-1}n^{m-1}}$ [1].

Le polynôme caractéristique du graphe biparti complet ${\displaystyle K_{m,n}}$ est : ${\displaystyle x^{m+n-2}(x^{2}-mn)}$. Ce polynôme caractéristique n'admet que des racines entières si, et seulement si, mn est un carré parfait. Le graphe biparti complet n'est donc un graphe intégral que dans ce cas.

Le théorème de Kuratowski qui caractérise les graphes planaires utilise le graphe ${\displaystyle K_{3,3}}$[2] - [3].

On note ${\displaystyle \mathrm {cr} (G)}$ le nombre de croisements du graphe ${\displaystyle G}$, le nombre minimal de croisements parmi les tracés possibles de ${\displaystyle G}$. Kazimierz Zarankiewicz[4], voulant résoudre le problème de l'usine de briques de Pál Turán, a établi la majoration suivante :

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }$

Cette inégalité est conjecturée être une égalité[5].