Изменения

Возьмем укладку графа <tex> G_1 </tex>. Добавив на нужных ребрах вершины степени <tex> 2 </tex> и удалив некотрые вершыни вершины степени <tex> 2 </tex> в старом графе получим укладку гомеоморфныого гомеоморфного графа <tex> G_2 </tex>, следовательно из планарности графа следует планарность гомеморфного графа и наоборот.

Покажем, далее, что в графе <tex> G''_1 </tex> и, аналогично, в графе <tex> G''_2 </tex> нет подграфов, гомеоморфных <tex> K_5 </tex> или <tex> K_{3,3} </tex>. Действительно, если в <tex> G''_1 </tex> имеется такой подграф, то в этом подграфе присутствует вновь присоединенное ребро, но это ребро <tex> e_1 </tex> можно заменить на цепь <br/><tex>a \to b \to ... \to v </tex>, <br/> взяв некоторую простую (b, v)-цепь <tex> P_2 </tex> в графе <tex> G'_2 </tex>. Следовательно, мы получили подграф в <tex> G </tex>, гомеоморфный <tex> K_5 </tex> или <tex> K_{3,3} </tex>, что невозможно. <br/> Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что ребро <tex> e_1 = av </tex> лежит на границе внешней грани(ее существование доказывается аналогично существованию такой укладки для вершины графа). Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> e_2 = vb </tex> лежит па границе внешпей внешней грани (рис. 5).