У теорії графів двогранний граф. або напіврегулярний двочастковий граф. є двочастковим графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в мають степінь , а вершини в степеня , тоді граф називається -двогранним.
Приклад Кожен повний двочастковий граф є -двогранним. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом. .
Кількість вершин
-двогранний граф має задовольняти рівняння . Це випливає з простого аргументу : кількість кінців ребер з дорівнює , кількість кінців ребер в дорівнює , і кожне ребро додає однакову кількість в обидва числа.
Симетрія Кожен регулярний двочастковий граф також є двогранним. Кожен реберно-транзитивний граф (забороняються графи з ізольованими вершинами), який не є також вершинно-транзитивним, повинен бути двогранним.. Зокрема, кожен реберно-транзитивний граф є або регулярним, або бірегулярним (двогранним).
Конфігурації Графи Леві геометричних конфігурацій є двогранними; двогранний граф — це граф Леві (абстрактної) конфігурації тоді й тільки тоді, коли його обхват становить не менше шести..
Посилання