Вложения графов

Докажите теорему 8.3 (формула Эйлера для плоских графов): если связный плоский граф порядка $n$ и размера $m$ имеет $f$ областей, то $n-m+f=2$.

Покажите, что если плоский граф порядка $n$ и размера $m$ имеет $f$ областей и $k$ компонент, то $n-m+f= k+1$.

Проверьте формулу Эйлера для плоских графов, изображённых на рис. 8-12:

Fig. 8-12

Найдите степени границ областей графов, изображённых на рис. 8-12 (см. задачу 8.3):

Покажите, что плоский граф 2-связен тогда и только тогда, когда граница каждой области является циклом.

Пусть $G=(V, E)$ — граф с числом вершинной связности $\boldsymbol {\kappa }(G)=2$, и пусть $x, y$ — две вершины, такие что $G-x-y$ несвязен и имеет компоненты $H_{i}(i=1,2, \ldots , k)$, где $H_{i}=\left(V_{i}, E_{i}\right)$ и $W_{i}=V_{i} \cup \left\{ x\right\} \cup \left\{ y\right\}$. Для каждого $i$ граф $G_{i}$ — это граф, порождённый множеством $W_{i}$, если вершины $x$ и $y$ смежны в $G$. Если эти две вершины несмежны, $G_{i}$ — граф, порождённый $W_{i}$ вместе с ребром $e$, соединяющим $x$ и $y$. Семейство $\left\{ G_{i}: i=1,2, \ldots , k\right\}$ называется гамачным разложением $G$ относительно разделяющего множества $\left\{ x, y\right\}$. Найдите гамачное разложение графа на рис. 8-13(a) относительно вершин $x$ и $y$, указанных на диаграмме.

Fig. 8-13

Покажите, что граф $G$ с $\kappa (G)=2$ планарен тогда и только тогда, когда каждый граф гамачного разложения графа $G$ относительно любого разделяющего множества, состоящего из двух вершин, планарен.

Покажите, что любая триангуляция с не менее чем четырьмя вершинами 3-связна.

Если $X$ — множество блоков, а $Y$ — множество точек сочленения графа $G=(V, E)$, то блок-точечный граф (BC-граф) графа $G$ — это двудольный граф $H=(X, Y, F)$, в котором ребро, соединяющее блок $B$ и точку сочленения $v$, существует тогда и только тогда, когда $v$ — вершина блока $B$. Постройте BC-граф графа $G$, изображённого на рис. 8-14(a).

Покажите, что если граф связен, то его BC-граф является деревом.

Блок $B$ графа называется концевым блоком, если $B$ содержит ровно одну точку сочленения. Покажите, что если граф имеет точку сочленения, то он имеет по меньшей мере два концевых блока.

Покажите, что граф $G$ планарен тогда и только тогда, когда каждый его блок планарен.

Fig. 8-14

Докажите теорему 8.4: число рёбер в триангуляции порядка $n$ (где $n \geq 3$ ) равно $3 n-6$.

Fig. 8-15

Покажите, что число рёбер в простом планарном графе порядка $n$ не превышает $3 n-6$.

Докажите теорему 8.5: графы $K_{5}$ и $K_{3,3}$ оба непланарны.

Покажите, что в простом планарном графе $G$ существует по меньшей мере четыре вершины со степенью не более 5. В частности, у каждого выпуклого многогранника есть по меньшей мере четыре вершины, смежные с тремя, четырьмя или пятью вершинами.

Приведите пример простого связного планарного графа, в котором степень каждой вершины не менее 5.

Приведите пример простого связного планарного графа, в котором степень каждой вершины равна ровно 4.

Покажите, что если простой граф $G$ имеет не менее 11 вершин, то $G$ и его дополнение не могут быть планарными графами одновременно.

Пусть $n_{i}$ — число вершин степени $i$ в триангуляции $G$ порядка $n$. Установите соотношение $3 n_{3}+2 n_{4}+n_{5}=n_{7}+2 n_{8}+3 n_{9}+\cdots +(n-6) n_{k}+12$, где $k$ — максимальная степень в $G$.

Покажите, что у каждого выпуклого многогранника есть по меньшей мере одна грань, граница которой состоит из трёх, четырёх или пяти рёбер. (Это аналогично факту, установленному в задаче 8.16, что у каждого выпуклого многогранника есть вершина, смежная с тремя, четырьмя или пятью вершинами.)

Покажите, что общее число вершин степени 3 и граней степени 3 в выпуклом многограннике не менее восьми.

Покажите, что существует только пять правильных многогранников.

Покажите, что у любого многогранного графа найдутся две смежные вершины, сумма степеней которых не превышает 13.

Граф $G$ называется минимально непланарным, если каждый его собственный подграф планарен. Покажите, что минимально непланарный граф является блоком.

Пусть $G$ — непланарный граф, не имеющий $K$-подграфа, такой что размер любого другого непланарного графа, не имеющего $K$-подграфа, больше размера $G$. Покажите, что $G$ 3-связен.

Покажите, что если $G$ — 3-связный граф с не менее чем пятью вершинами, то у него есть ребро $e$, такое что $G.e$ 3-связен.

Покажите, что если стягивание $G.e$ графа $G$ имеет $K$-подграф, то и $G$ имеет его.

Покажите, что если 3-связный граф $G$ не имеет $K$-подграфа, то он обладает выпуклой прямолинейной укладкой на плоскости.

Покажите, что 3-связность необходима в теореме Тутта.

Fig. 8-18

Докажите теорему 8.6 (теорема Куратовского—Понтрягина): граф планарен тогда и только тогда, когда он не имеет $K$-подграфа.

Докажите теорему 8.1 (теорема Фари—Штейна—Вагнера): любой простой планарный граф обладает прямолинейным представлением: он имеет укладку на плоскости, в которой каждое ребро изображается прямой линией.

(Граф конфликтов графа относительно одного из его циклов) Пусть $C$ — цикл в графе $G= (V, E)$. Кусок графа $G$ относительно $C$ — это либо подграф, состоящий из ребра (в $G$), соединяющего две несмежные вершины цикла $C$, либо подграф, образованный компонентой $H$ графа $G-C$ и всеми рёбрами графа $G$, инцидентными вершинам $H$. Вершина $v$ куска $P$ называется контактной вершиной куска $P$, если $v$ — вершина цикла. Любой кусок, содержащий более одной контактной вершины, называется сегментом графа $G$ относительно $C$. Два сегмента $S$ и $S^{\prime }$ находятся в конфликте, если ребро из $S$ и ребро из $S^{\prime }$ обязательно пересекаются (не в вершине), когда эти два сегмента укладываются по одну сторону (внутреннюю или внешнюю) от $C$. Пусть $X$ — множество всех сегментов относительно цикла $C$. Граф конфликтов с $X$ в качестве множества вершин строится следующим образом. Два сегмента соединяются ребром тогда и только тогда, когда они находятся в конфликте. Постройте граф конфликтов, показанный на рис. 8-19(a), относительно цикла $C: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1$.

Покажите, что если граф $G$ содержит $K_{5}$ или $K_{3.3}$ в качестве подграфа, то в $G$ существует цикл, относительно которого граф конфликтов не является двудольным.

Покажите, что граф планарен тогда и только тогда, когда его граф конфликтов относительно каждого его цикла двудолен.

Докажите, что граф конфликтов относительно любого цикла графа, изображённого на рис. 8-19(a), двудолен.

Покажите, что граф Хивуда (см. рис. 7-25) непланарен.

Покажите, что дополнение 3-мерного куба непланарно.

Приведите пример двух гомеоморфных образов графа, ни один из которых не является гомеоморфным образом другого.

Покажите, что если граф $G$ имеет $K_{3,3}$ в качестве подстягивания, то $G$ непланарен.

Покажите, что если граф $G$ имеет $K_{5}$ в качестве подстягивания, то $G$ непланарен.

Докажите теорему 8.7 (теорема Харари—Тутта—Вагнера): граф планарен тогда и только тогда, когда ни $K_{5}$, ни $K_{3,3}$ не являются подстягиванием графа $G$. (Иными словами, граф планарен тогда и только тогда, когда он не имеет подграфа, стягиваемого к $K_{5}$ или $K_{3,3}$.)

Используя формулу Эйлера, покажите, что граф Петерсена непланарен.

Покажите, что граф Петерсена непланарен, установив, что он имеет $K$-подграф.

Покажите, что граф Петерсена непланарен, показав, что граф конфликтов относительно одного из его циклов не является двудольным.

Покажите, что граф Петерсена непланарен, показав, что он стягиваем к $K_{5}$.

(Теорема Х. Пейтона Янга) Покажите, что 4-связный граф непланарен тогда и только тогда, когда он имеет $K_{5}$ в качестве подстягивания.

Планарный граф называется внешнепланарным, если он обладает укладкой на плоскости, при которой каждая вершина графа принадлежит границе одной и той же (как правило, внешней) области. Покажите, что граф внешнепланарен тогда и только тогда, когда он не имеет подграфа, являющегося гомеоморфным образом $K_{4}$ или $K_{2,3}$. (Эти два полных графа являются «запрещёнными графами» для внешнепланарности и играют примерно ту же роль, что $K_{5}$ и $K_{3,3}$ играют в вопросах, связанных с планарностью.)

Покажите, что граф $G$ внешнепланарен тогда и только тогда, когда ни $K_{4}$, ни $K_{2,3}$ не являются подстягиванием графа $G$.

Внешнепланарный граф называется максимальным внешнепланарным, если он теряет внешнепланарность при добавлении ребра, соединяющего любые две несмежные вершины. Пусть $G$ — внешнепланарный граф порядка $n$ и размера $m$ с $f$ областями. Покажите, что выполняются следующие свойства:

Покажите, что три условия, перечисленные в задаче 8.50, необходимы, но не достаточны для того, чтобы граф был максимальным внешнепланарным.

Два ребра графа образуют пересечение, если существует такая укладка графа, при которой эти два ребра пересекаются в точке, не являющейся вершиной. Если два ребра встречаются в точке пересечения, третье ребро не должно проходить через эту точку пересечения и не должно пересекать ни одно из этих двух рёбер в другой точке. Минимальное число пересечений рёбер среди всех укладок графа $G$, удовлетворяющих этому требованию, называется его числом пересечений $\boldsymbol {v}(\boldsymbol {G})$, которое равно нулю, если $G$ планарен. Найдите числа пересечений графов $K_{5}, K_{3.3}, K_{6}$ и $K_{3,4}$.

Граф $G=(V, E)$ называется $k$-дольным, если существует разбиение $V$ на $k$ подмножеств $V_{i}$, такое что каждое ребро из $E$ соединяет некоторую вершину из $V_{i}$ с некоторой вершиной из $V_{j}$, где $i \neq j$. Если каждое $V_{i}$ содержит $r_{i}$ вершин и если между каждой вершиной из $V_{i}$ (для каждого $i$) и каждой вершиной из $V_{j}$ для каждого $j$ (где $i \neq j$) есть ребро, мы получаем полный $k$-дольный граф $K\left(r_{1}, r_{2}, \ldots , r_{k}\right)$. Найдите число пересечений графа $K(3,2,2)$.

Найдите число пересечений графа Петерсена.

Толщиной $\boldsymbol {\theta }(\boldsymbol {G})$ графа $G$ называется минимальное число попарно рёберно непересекающихся остовных подграфов в разложении графа. Найдите толщину полного графа с $n$ вершинами, где $n \leq 8$.

Найдите толщину графа Петерсена.

Граф называется бипланарным, если его толщина равна 2. Покажите, что если $G$ — произвольный непланарный граф, существует бипланарный граф $H$, являющийся гомеоморфным образом $G$.

Если граф $G$ с $n$ вершинами имеет $m$ рёбер, покажите, что его толщина $\theta (G) \geq m /(3 n-6)$. Если граф двудолен, покажите, что $\theta (G) \geq m /(2 n-4)$.

Найдите нижнюю оценку толщины полного графа порядка $n$, где $n \geq 5$, используя результат задачи 8.58.

Найдите нижнюю оценку толщины полного двудольного графа $K_{m, n}$, используя результат задачи 8.58.

Покажите, что не существует плоского графа с пятью областями, такого что между каждой парой областей есть ребро.

Покажите, что планарный граф двудолен тогда и только тогда, когда его двойственный граф эйлеров.

Покажите, что если $G^{\prime }$ — геометрически двойственный граф связного планарного графа $G$, то $G$ является геометрически двойственным графу $G^{\prime }$.

Покажите, что если планарный граф 3-рёберно-связен, его геометрически двойственный граф прост.

Покажите, что множество рёбер связного плоского графа образует остовное дерево тогда и только тогда, когда множество двойственных рёбер оставшихся рёбер образует остовное дерево в геометрически двойственном графе.

Покажите, что множество рёбер плоского графа образует цикл тогда и только тогда, когда множество двойственных рёбер образует разрезающее множество в геометрически двойственном графе.

Покажите, что геометрически двойственный граф любого планарного графа $G$ совпадает с абстрактно двойственным графом $G$.

Покажите, что число рёбер, общих для цикла и разрезающего множества графа, всегда чётно.

Пусть $X$ — множество рёбер графа $G=(V, E)$. Покажите, что:

Покажите, что если $G^{*}$ — абстрактно двойственный граф $G$, то $G$ — абстрактно двойственный граф $G^{*}$. (Заметим, что здесь $G$ не обязательно связен, в отличие от задачи 8.63.)

Приведите пример плоского графа, для которого геометрически двойственный граф геометрически двойственного графа и абстрактно двойственный граф абстрактно двойственного графа не совпадают.

Покажите, что ни один из следующих графов не имеет абстрактно двойственного графа:

Покажите, что если граф $G$ имеет абстрактно двойственный граф, каждый подграф $G$ также имеет абстрактно двойственный граф.

Покажите, что если $G$ — гомеоморфный образ $H$ и $G$ имеет абстрактно двойственный граф, то $H$ также имеет абстрактно двойственный граф.

Докажите теорему 8.8 (теорема Уитни): граф планарен тогда и только тогда, когда он имеет абстрактно двойственный граф.

Докажите теорему 8.10 (теорема Гринберга—Козырева): если $C$ — произвольный гамильтонов цикл в гамильтоновом плоском графе порядка $n$, сумма индексов внутренних областей относительно $C$ и сумма индексов внешних областей относительно $C$ обе равны $(n-2)$.

Используя теорему Гринберга—Козырева, покажите, что плоский граф, изображённый на рис. 8-30, не является гамильтоновым.

Fig. 8-30

Покажите, что 3-связный кубический плоский граф, известный как граф Гринберга—Козырева, изображённый на рис. 8-31, не является гамильтоновым.

Покажите, что в гамильтоновом графе $G$, изображённом на рис. 8-32, любой гамильтонов цикл, содержащий ребро $e$, не содержит ребра $f$.

Покажите, что граф Тутта, изображённый на рис. 8-33, не является гамильтоновым.

Покажите, что плоский граф, изображённый на рис. 8-34, не является гамильтоновым.

Покажите, что не существует гамильтонова планарного графа с областями степеней 5 и 8 и одной областью степени 7.

Приведите пример максимального планарного графа, не являющегося гамильтоновым графом.

Докажите теорему 8.11: пусть $G$ — сеть с источником $s$ и стоком $t$, и пусть $G^{*}$ — её двойственная сеть. Пусть $d\left(k^{*}\right)$ — кратчайшее расстояние между $s^{*}$ и $k^{*}$ в $G^{*}$. Определим $x_{i j}=d\left(j^{*}\right)-d\left(i^{*}\right)$, где $\left\{ i^{*}, j^{*}\right\}$ — двойственное ребро, соответствующее ребру $\left\{ i, j\right\}$ в $G$. Тогда вектор $\left[x_{i j}\right]$ является максимальным потоком в $G$.

Найдите максимальный поток в плоской сети, изображённой на рис. 8-36(a), с вершиной 1 в качестве источника и вершиной 10 в качестве стока.

Докажите теорему 8.12: непланарные графы $K_{5}$ и $K_{3.3}$ тороидальны.

Fig. 8-37a

Найдите род графа $K_{7}$.

Покажите, что $K_{4,4}$ — тороидальный граф.

Приведите пример графа, у которого род меньше числа пересечений.

Покажите, что любой граф можно уложить в трёхмерном пространстве (не на поверхности) так, чтобы никакие два ребра не пересекались, кроме как, возможно, в вершине.

Покажите, что если связный граф $G$ рода $g$ уложен на поверхности рода $g$, каждая область, определяемая этой укладкой, является 2-клеткой.

Докажите теорему 8.13 (обобщённая формула Эйлера): если укладка связного графа порядка $n$ и размера $m$ на поверхности рода $g$ определяет $r$ областей, и если каждая область, определяемая этой укладкой, является 2-клеткой, то $n-m+r=2(1-g)$.

Покажите, что если связный граф порядка $n$, размера $m$ и рода $g$ уложен на поверхности рода $g$, и если число областей укладки равно $r$, то $n-m+r=2(1-g)$.

Найдите число 2-клеток, образующихся при укладке графа Петерсена на торе.

Если простой связный граф $G$ уложен на поверхности, найдите нижнюю оценку рода графа. Рассмотрите случай, когда $G$ двудолен.

Если простой связный граф $G$ уложен на поверхности, найдите верхнюю оценку числа рёбер. Рассмотрите случай, когда граф двудолен.

Простой связный граф порядка $n$, размера $m$ и рода $g$ называется максимальным $g$-графом, если $m=(3 n-2+ 2 g)$, когда он не двудолен, и $m=(2 n-4+4 g)$, когда он двудолен. Покажите, что $K_{7}$ и $K_{4,4}$ — максимальные тороидальные графы, а $K_{6}$ — нет.

Найдите нижнюю оценку рода полных графов:

Найдите нижнюю оценку рода $k$-мерного куба.

Если граница каждой грани плоского графа порядка $n$ содержит четыре ребра, покажите, что размер графа равен $2 n-4$.

Если плоский граф порядка $n$ 2-связен и ни одна грань не является треугольником, покажите, что размер графа не может превышать $2 n-4$.

Если 4-регулярный плоский граф имеет восемь граней, найдите число его вершин и рёбер.

Если 4-регулярный плоский граф имеет 10 граней, найдите число его вершин и рёбер.

Если граница каждой области связного плоского графа порядка $n$ и размера $m$ содержит $r$ рёбер, покажите, что $m(r-2)=r(n-2)$.

Если 3-регулярный связный плоский граф имеет 12 областей, найдите число его вершин и рёбер.

Если обхват (число рёбер в цикле с минимальным числом рёбер) связного графа порядка $n$ и размера $m$ равен $g$, докажите неравенство $m(g-2) \leq g(n-2)$.

Покажите, что граф с менее чем девятью рёбрами планарен.

Найдите число областей в планарном графе порядка $n$, если $(a)$ это триангуляция и $(b)$ это максимальный внешнепланарный граф.

Найдите число пересечений графа $K_{3.4}$.

Плоский граф 2-связен тогда и только тогда, когда его геометрически двойственный граф 2-связен.

Покажите, что не существует гамильтонова планарного графа с областями степеней 4 и 6 и одной областью степени 9.

Покажите, что планарный граф, изображённый на рис. 8-41, не является гамильтоновым.

Fig. 8-41

Покажите, что планарный граф, изображённый на рис. 8-42, не является гамильтоновым.

Fig. 8-42

Покажите, что планарный граф на рис. 8-43 не является гамильтоновым.

Fig. 8-43