Cтраница 3
Предположим, что G содержит, по крайней мере, четыре вершины. Случай трех или большего числа вершин оставляем для упражнения. Построим плоскую триангуляцию G, которая содержит G в качестве подграфа. Если R - грань G, a v и v2 - две вершины R, не связанные ребром, то соединим У. Получаем новый граф, который опять является обыкновенным. Продолжим такой процесс соединения несвязных пар вершин на грани, пока каждая пара вершин не будет связана ребром. После окончания процесса получим обыкновенный граф G с тем же самым числом вершин. Покажем, что G - плоская триангуляция, предварительно заметив, что если некоторая грань ограничена только одним ребром, то граф состоит из этого ребра и двух его вершин. Грань не может быть ограничена двумя ребрами, так так тогда граф содержал бы только три вершины. [31]