Изменения

Итак пусть граф <tex>G</tex> связен. Если <tex>G = K_1</tex>, то <tex>G</tex> очевидно планерен, поэтому предположим, что <tex>|EG| \ge 1</tex> , а значит имеется по-крайней мере один блок в <tex>G</tex>. Рассмотрим связный подграф <tex>T</tex> графа блоков и точек сочленений графа <tex>G</tex> такой, что <tex>\forall v</tex> - т.с. <tex>G</tex> имеем <tex>deg(v) \ge 2</tex>. Из [[Граф блоков-точек сочленения#lemma1|леммы]] и из связности <tex>T</tex> - получаем, что <tex>T</tex> &mdash; двудольное [[Дерево, эквивалентные определения|дерево]].

Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из блоков графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говритьговорить, что <tex>G'</tex> соответствует <tex>T</tex>).

Положим <tex>G_1</tex> &mdash; это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>v</tex> &mdash; т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg (v ) > 0</tex>, т.к. <tex>v</tex> - т.с., следовательно не висячая. Рассмотрим два случая:

#<tex>deg(v) = 2</tex> в <tex>T</tex>. Обозначим за <tex>T'</tex> <tex>T\backslash \{u,v\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме удаленной <tex>v</tex>) не уменьшилась, значит <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 2 = m - 2 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>{u. </tex> и <tex>v}</tex> по очереди были висячими вершинами <tex>T</tex> и <tex>T\backslash \{u\}</tex>.#<tex>deg (v) > 2</tex> в <tex>T</tex>. Обозначим за <tex>T'</tex> <tex>T\backslash \{u\}</tex>. Поскольку степень ни одной из т.с. <tex>G'</tex> принадлежащих <tex>T</tex> (кроме <tex>v</tex>, для нее степень уменьшилась ровно на <tex>1</tex>) не уменьшилась, а для вершины <tex>v</tex> в <tex>T'</tex> верно, что <tex>deg (v ) >= 2</tex>, то <tex>T'</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции. Заметим, что <tex>VT' = VT - 1 = m - 1 < m</tex>. Заметим также, что <tex>T'</tex> связен, т.к. <tex>u</tex> была висячей вершиной в <tex>T</tex>

Рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex> соответствующий дереву <tex>T'</tex>. Поскольку <tex>T' - </tex> связен, степени вершин в <tex>T'</tex> соответствующих т.с. графа <tex>G'</tex> удовлетворяют предположению индукциии, и очевидно , также как и <tex>T</tex> граф <tex>T'</tex> является подграфом графа блоков и точек сочленений <tex>G</tex>, получим, что <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>VT' < m</tex>.

Из определения ребер дерева блоков и точек сочленений получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> содержат имеют единственную общую точку {{-- -}} точку сочленения <tex>v</tex>. Поскольку множество блоков <tex>G'</tex> принадлежащих <tex>T</tex> состоит из <tex>G_1</tex> и множества блоков <tex>T'</tex>, то <tex>G' = \{G_1\}\cup \{G_2\}</tex>. <tex>G_1, G_2, G'</tex> удовлетворяют условию [[#l1|леммы I]], поэтому получим укладку <tex>G</tex> из укладок <tex>G_1, </tex> и <tex>G_2</tex> так , как это сделано в доказательстве леммы. получаем Получаем, что <tex>G'</tex> - планарен. А значит предположение индукции - верно.

Рассматривая в качестве <tex>T</tex> граф <tex>T_G</tex> блоков и точек сочленений <tex>G</tex>. По [[Граф блоков-точек сочленения|лемме]] <tex>T_G</tex> {{- --}} дерево, следовательно каждая его вершина имеет степень как минимум <tex>1</tex>. Поскольку граф <tex>G</tex> содержит хотя бы один блок. Если это единственный блок, то <tex>T_G</tex> не содержит ни одной точки сочленения. Если граф <tex>G</tex> содержит хотя бы <tex>2</tex> блока и, следовательно, хотя бы одну точку сочленения, то <tex>T_G</tex> &mdash; {{---}} дерево, содержащее хотя бы одно ребро. Поскольку в графе блоков и точек сочленений точки сочленений не могут быть висячими вершинами, то каждая из т.с. графа <tex>G</tex> принадлежащих <tex>T_G</tex> имеет степень как минимум <tex>2</tex>. планарен. Получаем, что <tex>T_G</tex> удовлетворяет условиям на <tex>T</tex> из предположения индукции, а значит <tex>G</tex> планарен.

'''Замечание.''' Доказательство теоремы непосредственно задает способ укладки графа <tex>G</tex>из имеющихся укладок его блоков.

Асанов М., Баранский В., Расин В. {{- --}} Дискретная математика: Графы, матроиды, алгоритмы — {{---}} Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.

H. Whitney {{- --}} Non-separable and planar graphs {{--- }} Trans. Amer. Math. Soc., 1932.