Дерево и плоские графы

В российской программе 8 класса («Вероятность и статистика», графы) деревом называют связный граф без циклов. Свойства дерева: между любыми двумя вершинами ровно одна цепь; у дерева с n вершинами ровно n − 1 рёбер; в дереве больше одной вершины есть вершина степени 1 (лист). Деревья описывают семейные древа, оглавления, схемы турниров на выбывание.

Остовное дерево связного графа — его часть, содержащая все вершины и являющаяся деревом. Чтобы получить остов графа из V вершин и E рёбер, надо убрать E − (V − 1) рёбер (по одному из каждого цикла).

Граф называют плоским, если его можно нарисовать на плоскости без пересечения рёбер. Для связного плоского графа выполняется формула Эйлера: В − Р + Г = 2, где В — число вершин, Р — число рёбер, Г — число граней, включая внешнюю. Эта формула относится к материалу повышенного уровня.