Двогранний граф

Види графів за їхніми автоморфізмами
відстанево-транзитивний	$\leftarrow$	сильно регулярний
$\downarrow$
симетричний (дуго-транзитивний)	$\leftarrow$	t-транзитивний, t ≥ 2
$\downarrow$(якщо зв'язний)
вершинно- та реберно-транзитивний	$\rightarrow$	реберно-транзитивний і регулярний	$\rightarrow$	реберно-транзитивний
$\downarrow$		$\downarrow$
вершинно-транзитивний	$\rightarrow$	регулярний
$\uparrow$
граф Келі		кососиметричний		асиметричний

У теорії графів двогранний граф або напіврегулярний двочастковий граф $G=(U,V,E)$ є двочастковим графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в $U$ мають степінь $x$, а вершини в $V$ степеня $y$, тоді граф називається $(x,y)$-двогранним.

Граф ромбододекаедру є двогранним (бірегулярним).

Приклад

Кожен повний двочастковий граф $K_{a,b}$ є $(b,a)$-двогранним. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом .

Кількість вершин

$(x,y)$-двогранний граф $G=(U,V,E)$ має задовольняти рівняння $x|U|=y|V|$. Це випливає з простого аргументу подвійного підрахунку: кількість кінців ребер з $U$ дорівнює $x|U|$, кількість кінців ребер в $V$ дорівнює $y|V|$, і кожне ребро додає однакову кількість в обидва числа.

Симетрія

Кожен регулярний двочастковий граф також є двогранним. Кожен реберно-транзитивний граф (забороняються графи з ізольованими вершинами), який не є також вершинно-транзитивним, повинен бути двогранним. Зокрема, кожен реберно-транзитивний граф є або регулярним, або бірегулярним (двогранним).

Конфігурації

Графи Леві геометричних конфігурацій є двогранними; двогранний граф — це граф Леві (абстрактної) конфігурації тоді й тільки тоді, коли його обхват становить не менше шести.