Планарный граф

Планарный граф — граф который можно изобразить на плоскости без пересечения ребер (кроме как в вершинах). Существует критерий планарности: граф планарен тогда и только тогда, когда он не содержит подграфы $$$K_5$$$ и $$$K_3,_3$$$. Где $$$K_5$$$ — полный граф на 5 вершинах, $$$K_3,_3$$$ полный двудольный граф на 6 вершинах (по 3 в каждой доле).

Формула Эйлера

Если граф на $$$V$$$ вершинах с $$$E$$$ ребрами планарен, то количество граней, на которые граф разбивает плоскость $$$F = E - V + 2$$$.