42
правки
Изменения
Нет описания правки
Граф [[Укладка_графа_на_плоскости| планарен]] тогда и только тогда, когда он не содержит подграфов, [[Укладка графа на плоскости #def_hmp| гомеоморфных]] <tex> K_{5} </tex> или <tex> K_{3, 3} </tex> .
|proof =
Заметим, что из планарности графа следует планарность гомеморфного гомеоморфного графа и наоборот. В самом деле, пусть <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>]].
