Рассмотрим изображения графа G. На рисунке 34 изображен граф G, некоторые ребра его пере­секаются. На рисунке 35 этот же граф G изображен так, что его ребра не пересекаются.
Граф на рисунке 40 является плоским представлением графа на рисунке 39.
                                          
                             Рис.39                               рис. 40
Граф G называют плоским,если его можно нарисовать на пло­скости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины.
Примерами плоских графов являются простые циклы, деревья, лес.
В качестве характеристики плоского представления графа вво­дится понятие грани.
Гранью в плоском представлении графа G называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
В качестве грани можно рассматривать и часть плоскости, рас­положенную «вне» плоского представления графа; она ограничена «изнутри» простым циклом и не содержит в себе других циклов. Эту часть плоскости называют «бесконечной» гранью.
                                             
                                                           Рис. 41
На рисунке 41 часть бесконечной грани заштрихована.
Дерево и лес имеют одну бесконечную грань.
                                                        
                                                           Рис. 42
Задание 7.1. На рисунке 42 плоское представление графа G.  Назовите его грани.
Ответ: (1, 7, 4, 1), (1, 3, 2, 4, 1), (1, 2, 3, 1), (2, 6, 5, 4, 2), (1, 2, 6, 5, 4, 7, 1).
Почему часть пло­скости, ограниченная простым циклом (1, 2, 4, 1), не явля­ется гранью?
Потому, что она содержит внутри себя цикл (1, 2, 3, 1).
Задание 7.2.
                                                          
                                                            Рис. 43
Назовите все грани графа.
Ответ: (1, 2, 3, 4), (1, 2, 3, 4, 5, 1).
 Почему часть плоскости, ограниченная простым циклом (1, 2, 3, 4, 5, 1), является гранью?
Потому что ребро (4, 5), расположенное внутри грани, не образует цикла.
Задание 7.3.
                                    
                                                       Рис. 44
Является ли часть плоскости, заштри­хованная на рисунке 44 гранью?
Ответ: Не является, так как она не огра­ничена изнутри простым циклом.
Задача 7.1.
Мэрия решила построить в каждом квартале города, имеющего 155
перекрестков и 260 отрезков улиц между перекрестками, универсам.
Сколько будет построено универсамов?
Решение.
Карту города можно считать плоским графом G, в котором перекрестки будут вершинами, а отрезки улиц — ребрами.
Плоский граф, изображенный на рис. 45, имеет 3 грани, причем грань 1 – внешняя, а грани 2 и 3 — внутренние.

      Рис 45
Теорема 10. Формула Эйлера. Для всякого связного плоского графа верно равенство: n – m + f = 2, где n – число вершин m — число ребер, a f— число граней графа.
Доказательство.
Подграф графа G, содержащий все вершины графа, называется остовным. Если оставный подграф является деревом, то он называется остовным деревом.
Рассмотрим остовное дерево Тграфа G. Очевидно, что граф Тимеет n вершин и одну грань (внешнюю). Поскольку Т – дерево, то число ребер Т равно (n-1). Поэтому для графа Тдоказываемая формула верна. Теперь будем поочеред­но добавлять к Т недостающие ребра графа G. При каждом добавлении число вершин не метется, а число ребер и граней увеличивается на еди­ницу. Это значит, что доказываемая формула будет верна для всякого графа, получаемого в результате операций добавления ребер, а, значит, и для исходного графа. Теорема доказана.
Поскольку кварталы города соответствуют внутренним граням плоского графа G, то найдем число граней по формуле Эйлера. Граф G имеет 155 вершин и 260 ребер. Число граней в нем: f = m – n + 2 = 260 - 155 + 2 = 107.
В городе нужно построить 106 универсамов.
Задача 7.2.
Печатная плата представляет собой пластинку из изолирующего материала, в специально изготовленные гнезда которой устанавливают электронные приборы. В качестве проводников, соединяющих эти приборы,  служат напыленные металлические дорожки. Поскольку проводники не изолируются, то дорожки не должны пересекаться. Ес­ли это может произойти, то одну из дорожек переносят на другую сто­рону платы. Конструктор Иванов придумал хорошую схему печатной платы, которая состоит из 12 приборов и 32 проводников, соединяю­щих их. Можно ли изготовить такую плату так, что все проводники будут расположены на одной ее стороне?
Решение.
Схему печатной платы можно представить в виде графа, вер­шины которого будут  изображать приборы, а ребра — проводники, их соединяющие. Решение задачи сводится к  ответу на вопрос: будет ли граф G, изображающий плату инженера Иванова, плоским?
Докажем следующее соотношение: предложение 3: для связного плоского гра­фа, содержащего n вершин и m ребер, при n ? 3 выполняется неравен­ство m ? 3n – 6.
Доказательство. Пусть   Г1, Г2, …, Ff— грани графа G, и m1, m2, ..., mf— число ребер ограничивающих, соответственно, каждую грань. Найдем сумму S = m1 + m2 + ... + mf.
Поскольку всякая грань графа ограничена, по крайней мере, тремя ребрами, то 3f ? S. С другой стороны, каждое ребро принадлежит или двум граням, или одной грани, т.е. в сумме S учитывается два раза или один. Поэтому S ? 2m. Мы получили, что 3f ? 2m. Далее воспользуемся формулой Эйлера:
f = m – n + 2,
3f = 3m – 3n + 6,
2m ? 3m – 3n + 6,
m ? 3n – 6.
Для n = 3неравенство проверяется непосредственно.
Неравенство доказано.
Для графа G, описывающего плату инженера Иванова, n = 12, m = 32, и полученное неравенство не выполняется.
Поэтому граф Gне является плоским и изготовить односторон­нюю плату невозможно.
Задача 7.3.
Инженер Иванов (см. предыдущую задачу) усовершенствовал свою плату. Теперь она имеет 9 приборов и 17 проводников (схему платы см. на рис. 46). Можно ли изготовить плату так, чтобы все проводники раз­мещались на одной ее стороне?

        Рис 46.
Решение.
Будем считать схему платы графом G. Неравенство m ? 3n – 6 не позволяет ответить, является ли граф G плоским, поскольку 17 ? 3*9 – 6 = 21.
Рассмотрим подграф графа G, выделенный жирными линиями на рисунке 47.
 
               рис. 47
Этот подграф можно получить из полного графа с пятью вершинами (К5), поставив на некото­рых его ребрах дополнительные вершины. (На рисунке вершины графа К5выделены, а дополнительные вершины помечены знаком "+"). Введе­ние дополнительных вершин не может превратить неплоский граф К5 в плоский. Следовательно, граф G, подграфом которого является неплоский граф, также неплоский. Это означает, что изготовить одно­стороннюю плату невозможно.
Известна теорема, описывающая строение плоских графов. Разобьем некоторые из ребер графов К3,3 и К5новыми вершинами (см. рис. 48). Получившиеся графы будем называть, соответственно, графами типов К3,3 и К5.

Рис. 48

Теорема 11. Теорема Понтрягина-Куратовского (1927,1930 г.). Граф является плоским тогда и только тогда, когда он не содержит подграфов типов К3,3 или К5.