272
правки
Изменения
Нет описания правки
Положим <tex>G_1</tex> — это блок графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex> (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a <tex>v</tex> {{---}} т.с. в <tex>G'</tex> смежная с <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. блоки графа <tex>G'</tex> совпадают с блоками графа <tex>G</tex>. Заметим, что <tex>deg(v) > 1</tex>, т.к. <tex>v</tex> {{---}} т.с., следовательно не висячая. Рассмотрим два случая:
#<tex>deg(v) = 2</tex> в <tex>T</tex> (рис. 2). Обозначим за <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>.[[Файл: Planar vertex biconnected 2.png|200px300px|center|thumb|рис. 2. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]#<tex>deg (v) > 2</tex> в <tex>T</tex> (рис. 3). Обозначим за <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>.[[Файл: Planar vertex biconnected 3.png|200px300px|center|thumb|рис. 3. Красные {{---}} точки сочленений. Голубые {{---}} блоки.]]
Рассмотрим подграф <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>.
