Изменения

Возьмем укладку Заметим, что из планарности графа следует планарность гомеморфного графа и наоборот. В самом деле, пусть <tex> G_1 -</tex>плоский граф. Добавив Если добавить на нужных ребрах вершины степени <tex> 2 </tex> и удалив удалить некотрые вершины степени <tex> 2 </tex> в старом графе<tex> G_1 </tex>, получим укладку гомеоморфного графа <tex> G_2 </tex>. Следовательно Таким образом, доказательство достаточности следует из планарности графа следует планарность гомеморфного графа и наоборот. Поэтому доказательство необходимости можно посмотреть [[Непланарность_K5_и_K3,3| здесьнепланарности <tex>K_5</tex> и <tex>K_{3, 3}</tex>]], докажем достаточность.

Докажем неоходимость. От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>.  Пусть <tex> G </tex> — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.