Graphe birégulier

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).