Максимальным планарным графом называется планарный граф, который при добавлении любого ребра перестает быть планарным.
Из определения следует, что в максимально планарном графе все грани являются треугольниками (гранями с тремя вершинами):
если грань содержит четырехугольник (или многоугольник с большим числом сторон), то можно добавить ребро , не меняющее планарность графа, но лишающее свойства графа быть максимально планарным графом.
Пример 1. В следующий граф можно добавить только одно ребро, после которого этот граф обращается в граф .
Максимальным планарным двудольным графом называется планарный двудольный граф, который при добавлении любого ребра перестает быть планарнымдвудольным графом.
Если – максимальный планарный двудольный граф, то каждая ее грань является четырехугольником:
Пример 2. В следующий граф можно добавить только одно ребро, после которого этот граф обращается в граф :
Следствие 2. Если – планарный -граф и , то
.
Доказательство. Наибольшим числом ребер в плоском графе обладает граф, у которого все грани – треугольники. В максимальном планарном графе все грани – треугольники. Подставим в (2) . Получим .
Следствие 3. Если – планарный двудольный граф, то -граф, то
.
Доказательство. Наибольшим числом ребер в плоском двудольном графе обладает граф, у которого все грани – четырехугольники. В максимальном планарном графе все грани – четырехугольники. Подставим в (2) . Получим .
Теорема 2. Графы и не планарные.
Доказательство. Если (5,10)-граф планарный, то не выполняется следствие 2: .
Если (6,9)-граф планарный, то не выполняется следствие 3: .
Теорема Куратовского. Граф планарен тогда и только тогда, когда не содержит подграфа, гомеоморфного или .