Graphe birégulier

Dans la théorie des graphes, un graphe birégulier^[1] est un graphe biparti dans lequel tous les sommets de chacune des deux parties du graphe ont le même degré. Notons ${\displaystyle U}$ et ${\displaystyle V}$ les deux parties d'un graphe birégulier. Si le degré des sommets de ${\displaystyle U}$ est ${\displaystyle x}$ et si le degré des sommets de ${\displaystyle V}$ est ${\displaystyle y}$, le graphe est dit ${\displaystyle (x,y)}$-birégulier.

Tout graphe biparti complet ${\displaystyle K_{a,b}}$ (figure) est ${\displaystyle (a,b)}$-birégulier^[2].

Le graphe du dodécaèdre rhombique (figure) est ${\displaystyle (3,4)}$-birégulier^[3]. En effet, ses sommets se répartissent en deux ensembles :

• l'ensemble ${\displaystyle U}$ des sommets de degré 4 ;
• l'ensemble ${\displaystyle V}$ des sommets de degré 3.

Aucun sommet de degré 4 n'est lié par une arête à un autre sommet de degré 4 ; aucun sommet de degré 3 n'est lié par une arête à un autre sommet de degré 3 : ce graphe est bien biparti.

Un graphe birégulier de parties ${\displaystyle U}$ et ${\displaystyle V}$ vérifie l'égalité ${\displaystyle deg(U)\cdot |U|=deg(V)\cdot |V|}$.

Par exemple, dans le dodécaèdre rhombique, on a 6 sommets de degré 4 et 8 sommets de degré 3, il vérifie bien ${\displaystyle 6\times 4=8\times 3}$.

On peut prouver cette égalité par double dénombrement :

• le nombre d'extrémités des arêtes aboutissant dans ${\displaystyle U}$ est ${\displaystyle deg(U)\cdot |U|}$ ;
• le nombre d'extrémités des arêtes aboutissant dans ${\displaystyle V}$ est ${\displaystyle deg(V)\cdot |V|}$ ;
• chaque arête a une extrémité et une seule dans ${\displaystyle U}$ et une extrémité et une seule dans ${\displaystyle V}$, donc ces deux nombres sont égaux.

• Un graphe ${\displaystyle n}$-régulier biparti est ${\displaystyle (n,n)}$-birégulier.
• Un graphe arête-transitif (en excluant les graphes avec des sommets isolés) qui n'est pas aussi sommet-transitif est birégulier^[2].
• En particulier, un graphe sommet-transitif est soit régulier, soit birégulier.
• Les graphes de Levi de configurations géométriques sont biréguliers.
• Un graphe birégulier est le graphe de Levi d'une configuration géométrique (abstraite) si et seulement si sa maille vaut au moins six^[4].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graphe birégulier » (voir la liste des auteurs).

• Portail des mathématiques