Как доказать утверждение?

Question

[NoName]

Существует граф с n вершинами, причем 3 < n < 8. Существует также дополнительный граф этого графа(т.е граф с теми же вершинами из первоначального графа, в котором есть ребра, которых нет в первоначальном графе). Как доказать, что хотя бы один из них планарен?

Answer 1

[Wataru]

Смотрите критерии планарности - надо плясать от них.

Например, если взять первый критерий - граф не содержит подгарфа, который есть подразделение K5 или K3,3.

Очевидно, что n=4 всегда планарен сам граф. Доказывать нечего. Остались случаи n=5,6,7.

Если сам граф не содержит такого - то он уже планарен, доказывать нечего. Если же сам граф содержит K5 или K3,3 то вам надо доказать, что дополнительный граф не может содержать такие подграфы.

n=8, очевидно, тут не подходит, потому что можно взять K5, прикрутить к нему рядом K3 (Без новых ребер между кликами). Дополнительный граф при этом будет K5,3 - который содержит в себе K3,3.

Советую рассмотреть 3 случая и доказать что они все не возможны. Граф и дополнительный граф содержат по K5; оба содержат по K3,3; один содержит K5, а другой K3,3.

Например, первый случай весьма прост - при n<8 подграфы пересекаются как минимум по 3 вершинам. В прямом графе из-за K5 они обязаны иметь между собой ребра, а из-за K5 в дополнительном графе - они обязаны не иметь между собой ребер. Противоречие.