Graphe birégulier

Dans la théorie des graphes, un graphe birégulier est un graphe biparti dans lequel tous les sommets de chacune des deux parties du graphe ont le même degré. Notons et les deux parties d'un graphe birégulier. Si le degré des sommets de est et si le degré des sommets de est , le graphe est dit -birégulier. vignette|Le graphe biparti complet est -birégulier. Tout graphe biparti complet (figure) est -birégulier. vignette|gauche|Le graphe du dodécaèdre rhombique est birégulier. Le graphe du dodécaèdre rhombique (figure) est -birégulier. En effet, ses sommets se répartissent en deux ensembles : l'ensemble des sommets de degré 4 ; l'ensemble 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 et vérifie l'égalité . 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 . On peut prouver cette égalité par double dénombrement : le nombre d'extrémités des arêtes aboutissant dans est ; le nombre d'extrémités des arêtes aboutissant dans est ; chaque arête a une extrémité et une seule dans et une extrémité et une seule dans , donc ces deux nombres sont égaux. Un graphe -régulier biparti est -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. 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.