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