| Математический сборник |
|
|
|
|
|
О количестве независимых и Д. С. Талецкий Лаборатория алгоритмов и технологий анализа сетевых структур, Национальный исследовательский университет "Высшая школа экономики", г. Нижний Новгород
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 11, Pages DOI: https://doi.org/10.4213/sm9870e 
Реферативные базы данных:
     § 1. ВведениеНезависимым множеством (сокращенно НМ) графа называется произвольное подмножество попарно несмежных его вершин. Количество всех НМ графа $G$ обозначается через $i(G)$. Для $k \geqslant 1$ $k$-доминирующим множеством (сокращенно $k$-ДМ) графа $G$ называется такое его подмножество вершин $D_k$, что каждая вершина не из $D_k$ смежна хотя бы с $k$ вершинами из $D_k$. Количество всех $k$-ДМ графа $G$ обозначается через $\partial_k(G)$. Граф называется $k$-регулярным, если степени всех его вершин равны некоторому целому числу $k \geqslant 0$, и называется нерегулярным, если в нем найдутся две вершины разных степеней. На сегодняшний день известно большое количество результатов, посвященных перечислению НМ в графах из тех или иных классов. При всех $n \geqslant 1$ граф-звезда и простой путь, как известно, содержат максимально и минимально возможные количества НМ в классе $n$-вершинных деревьев соответственно (см. [1]). В работе [2] для любых $n,d \geqslant 3$ была описана структура $n$-вершинных деревьев с максимальной степенью вершин $d$, содержащих максимально возможное количество НМ среди всех таких деревьев. В работах [3]–[6] была получена асимптотически точная верхняя оценка количества НМ в $n$-вершинном $k$-регулярном графе и описаны соответствующие экстремальные графы. Многие другие результаты такого рода упомянуты в недавнем обзоре [7]. Перечислительных результатов, связанных с $k$-ДМ, известно значительно меньше, и почти все они касаются случая $k=1$. В классе $n$-вершинных деревьев наибольшее количество 1-ДМ содержит граф-звезда, при этом существует экспоненциально много деревьев, содержащих минимально возможное количество 1-ДМ среди графов этого класса (см. [8]). Позднее в работе [9] данный результат был обобщен на класс связных графов. В недавней работе [10] для всех $n,k \geqslant 2$ была описана структура деревьев, содержащих максимально и минимально возможные количества $k$-ДМ среди всех $n$-вершинных деревьев. При любом $k \geqslant 1$ количество НМ $k$-регулярного графа совпадает с количеством его $k$-ДМ. Действительно, из определений НМ и $k$-ДМ следует, что дополнение любого НМ $k$-регулярного графа является его $k$-ДМ и наоборот. На рис. 1 изображен 3-регулярный граф, вершины которого разбиваются на НМ $\{v_3,v_5\}$ (его элементы выделены серым цветом) и 3-ДМ $\{v_1,v_2,v_4,v_6\}$. Значительно более сложным является вопрос о соотношении количества НМ и количества $k$-ДМ в нерегулярных графах со средней степенью вершин $k$. По мнению автора настоящей статьи, имеет место следующий факт. Предложение. Если средняя степень вершин графа $G$ не превосходит натурального числа $k \geqslant 1$, то имеет место неравенство $\partial_k(G) \leqslant i(G)$. При этом равенство возможно, если и только если граф $G$ является $k$-регулярным. Работа посвящена доказательству данного утверждения в случае $k \in \{1,2\}$. В § 2 приведены некоторые стандартные обозначения теории графов. В § 3 введены дополнительные обозначения, связанные с НМ и $k$-ДМ в графах, а также доказан ряд вспомогательных утверждений. В § 4 доказан основной результат работы. В § 5 обсуждаются перспективы дальнейших исследований в случае $k \geqslant 3$. § 2. Некоторые определения и обозначенияЧерез $N_G(v)$ обозначается открытая окрестность вершины $v$ в графе $G$, т.е. множество всех смежных с $v$ вершин. Замкнутой окрестностью вершины $v$ в графе $G$ называется множество $N_G[v]= N_G(v) \cup \{v\}$. Для произвольного множества вершин $A \subseteq V(G)$ определим его замкнутую окрестность как $N_G[A]=\bigcup_{a \in A} N_G[a]$. Если из контекста ясно, какой граф имеется в виду, мы будем использовать обозначения $N(v)$, $N[v]$ и $N[A]$ соответственно. Через $P_n$, $C_n$ и $K_n$ обозначаются цепь, цикл и полный граф на $n$ вершинах соответственно. Для смежных вершин $u$, $v$ графа $G$ через $G \setminus u$ обозначается результат удаления из $G$ вершины $u$ и всех инцидентных ей ребер, а через $G - uv$ обозначается результат удаления из $G$ ребра $uv$. Для произвольного подграфа $H$ графа $G$ через $G \setminus H$ обозначается граф, порожденный вершинами множества $V(G) \setminus V(H)$. Через $K_n - e$ обозначается результат удаления ребра из полного графа $K_n$. Треугольником в графе называется его подграф $K_3$. Для $m \geqslant 1$ и графа $G$ через $mG$ обозначается граф с $m$ компонентами связности, каждая из которых изоморфна $G$. Cреднюю степень вершин графа $G$ обозначим через $\overline{d}(G)$. Вершина графа называется изолированной (соответственно висячей), если она имеет степень $0$ (соответственно степень $1$). Деревом называется связный граф без циклов. Как известно, связный граф $G$ является деревом, если и только если $\overline{d}(G) < 2$. Кроме того, каждое дерево содержит хотя бы две висячие вершины. Через $G \cong H$ обозначается изоморфизм графов $G$ и $H$. Граф $H'$ называется остовным подграфом $G$, если он может быть получен из $G$ путем удаления нескольких ребер. Граф $H''$ называется порожденным подграфом $G$, если он может быть получен из $G$ путем удаления нескольких вершин вместе со всеми инцидентными им ребрами. § 3. Предварительные результаты3.1. Семейства $k$-доминирующих и независимых множеств графаОбозначим через $\mathfrak{D}_k(G)$ и $\mathfrak{I}(G)$ соответственно семейства всех $k$-доминирующих и независимых множеств графа $G$, а через $\partial_k(G)$ и $i(G)$ соответственно мощности этих семейств. Через $\mathfrak{D}_k(G,A^+_1,\dots,A^+_m,B^-_1,\dots,B^-_s)$ обозначим семейство всех таких $k$-ДМ графа $G$, что они содержат все вершины множеств $A_1,\dots,A_m$ и не содержат ни одной вершины множеств $B_1,\dots,B_s$. Если множество $A$ состоит из одного элемента $a$, то будем использовать обозначение $\mathfrak{D}_k(G,a^+)$ вместо $\mathfrak{D}_k(G,A^+)$. Положим
$$
\begin{equation*}
\partial_k(G,A^+_1,\dots,A^+_m,B^-_1,\dots,B^-_s)= |\mathfrak{D}_k(G,A^+_1,\dots,A^+_m,B^-_1,\dots,B^-_s)|.
\end{equation*}
\notag
$$
Аналогичным образом введем обозначения $\mathfrak{I}(G,A^+_1,\dots,A^+_m,B^-_1,\dots,B^-_s)$ и $i(G,A^+_1,\dots,A^+_m,B^-_1,\dots,B^-_s)$ для семейства всех НМ графа $G$ и его мощности соответственно при заданных ограничениях. Отметим несколько простых фактов. Лемма 1. Для графа $G$, целого числа $k \geqslant 1$ и множеств $A,B,C \subseteq V(G)$ имеют место равенства Доказательство. Из определения семейства $\mathfrak{D}_k(G)$ следует, что для любого множества $X \subseteq C$ найдется в точности $\partial_k(G,A^+,B^-,X^+,(C \setminus X)^-)$ $k$-ДМ $D \in \mathfrak{D}_k(G,A^+,B^-)$ графа $G$ таких, что $D \cap C=X$, откуда и следует равенство (3.1). Равенство (3.2) доказывается аналогично.
Лемма доказана. Замечание 1. Если $C=\{c\}$, то равенства (3.1) и (3.2) примут вид Лемма 2. Для графа $G$, целого числа $k \geqslant 1$, множеств $A_1 \subseteq A_2 \subseteq V(G)$ и $B_1 \subseteq B_2 \subseteq V(G)$ имеют место неравенства Неравенства (3.5) и (3.6) с очевидностью следуют из включений
$$
\begin{equation*}
\mathfrak{D}_k(G,A^+_2,B^-_2) \subseteq \mathfrak{D}_k(G,A^+_1,B^-_1),\qquad \mathfrak{I}(G,A^+_2,B^-_2) \subseteq \mathfrak{I}(G,A^+_1,B^-_1).
\end{equation*}
\notag
$$
Лемма 3. Для графа $G$, целого числа $k \geqslant 1$ и множеств $A, B, C \subseteq V(G)$ таких, что $B \cap C=\varnothing$, имеют место неравенства Доказательство. Докажем неравенство (3.7). Из определений $k$-ДМ и семейства $\mathfrak{D}_k(G)$ следует, что для любого множества $D \in \mathfrak{D}_k(G,A^+,B^-,C^-)$ верно включение $D \cup C \in \mathfrak{D}_k(G,A^+,B^-,C^+)$, что и требовалось.
Докажем неравенство (3.8). Если либо множество $A \cup C$ не является независимым, либо $A \cap B \neq \varnothing$, то $i(G,A^+,B^-,C^+)=0$ и доказывать нечего. Иначе выполнены равенства
$$
\begin{equation*}
\begin{gathered} \, i(G,A^+,B^-,C^+)=i(G \setminus (N[A] \cup B \cup N[C])), \\ i(G,A^+,B^-,C^-)=i(G \setminus (N[A] \cup B \cup C)). \end{gathered}
\end{equation*}
\notag
$$
Так как граф $G \setminus (N[A] \cup B \cup N[C])$ является подграфом графа $G \setminus (N[A] \cup B \cup C)$, то и неравенство (3.8) выполнено.
Лемма доказана. Лемма 4. Если граф $H$ является подграфом графа $G$, то $\partial_k(H) \leqslant \partial_k(G)$ при любом целом $k \geqslant 1$. Доказательство. Из определения $k$-ДМ следует, что при добавлении ребра в граф количество его $k$-ДМ не убывает. Следовательно, если $H$ является остовным подграфом $G$, то верно $\mathfrak{D}_k(H) \subseteq \mathfrak{D}_k(G)$, откуда получаем $\partial_k(H) \leqslant \partial_k(G)$. Осталось рассмотреть случай, когда множество $U=V(G) \setminus V(H)$ непусто. Нетрудно проверить, что по определению $k$-ДМ для любого множества $D \in \mathfrak{D}_k(H)$ верно включение $D \cup U \in \mathfrak{D}_k(G)$. Тогда из неравенства (3.5) следует соотношение $\partial_k(H) \leqslant \partial_k(G,U^+) \leqslant \partial_k(G)$.
Лемма доказана. Замечание 2. Интересно, что для НМ аналогичное лемме 4 утверждение неверно. Как известно (см. [7; предложение 1]), если граф $H$ является остовным подграфом графа $G$, то имеет место неравенство $i(H) \geqslant i(G)$, поскольку при удалении ребра из графа количество его НМ строго возрастает. Если же $H$ является порожденным подграфом $G$, то имеет место неравенство $i(H) \leqslant i(G)$, поскольку при удалении вершины из графа количество его НМ строго убывает. Лемма 5. Пусть даны граф $G$ и целое число $k \geqslant 1$, а также множества $A,B \subset V(G)$ и $X=\{x_1,\dots,x_s\} \subseteq V(G) \setminus (A \cup B)$, где $s \geqslant 2$. Положим $X_i=X \setminus \{x_i\}$, $1 \leqslant i \leqslant s$, тогда имеет место неравенство Доказательство. Из (3.7) следует неравенство
$$
\begin{equation*}
\partial_k(G,A^+,B^-,x^+_s,X^-_s) \leqslant \partial_k(G,A^+,B^-,x^-_{1},X^+_{1}),
\end{equation*}
\notag
$$
а также для всех $1 \leqslant i \leqslant s-1$ верно
$$
\begin{equation*}
\partial_k(G,A^+,B^-,x^+_i,X^-_i) \leqslant \partial_k(G,A^+,B^-,x^-_{i+1},X^+_{i+1}),
\end{equation*}
\notag
$$
откуда и следует неравенство (3.9).
Лемма доказана. Для графа $G$, его подграфа $G'$, полученного удалением ребер и, возможно, изолированных вершин $G$, а также множеств $A, B \subseteq V(G')$ введем обозначение
$$
\begin{equation}
\partial^*_k(G,G',A^+,B^-)=\partial_k(G,A^+,B^-) - \partial_k(G',A^+,B^-).
\end{equation}
\tag{3.10}
$$
Замечание 3. Пусть $k=2$, $A=\{a\}$, $B=\{b\}$, а граф $G'$ получен из графа $G$ удалением ребра $ab$ и, возможно, изолированных вершин. В этом случае величина $\partial^*_2(G,G',a^+,b^-)$ равна количеству множеств $D \in \mathfrak{D}_2(G,a^+,b^-)$ таких, что в графе $G$ вершина $b$ смежна ровно с одной вершиной $D$, отличной от $a$. 3.2. Свойства независимых множествСледующий хорошо известный факт (см. [7; предложение 4]) приводится без доказательства. Из (3.8) следует, что для любой вершины $v$ графа $G$ верно неравенство $i(G,v^-) \geqslant i(G,v^+)$. Для того чтобы оценить разность $i(G,v^-) - i(G,v^+)$, нам потребуется более сильное утверждение. Лемма 7. Пусть вершина $v$ графа $G$ смежна с вершинами $v_1,v_2,\dots,v_s$ степеней $d_1,d_2,\dots,d_s$ соответственно. Тогда имеет место неравенство Доказательство. Положим $V_j=N[v] \setminus v_j$, $1 \leqslant j \leqslant s$. Легко видеть, что $i(G,v^+) =i(G,N[v]^-)$, а семейство $\mathfrak{I}(G,v^-) \setminus \mathfrak{I}(G,N[v]^-)$ состоит в точности из тех НМ $G$, которые содержат хотя бы одну вершину из окрестности $N(v)$. Таким образом, имеет место неравенство
Для фиксированного $1 \leqslant j \leqslant s$ докажем, что
$$
\begin{equation*}
i(G,v^+_{j},V^-_j) \geqslant \frac{1}{2^{d_j-1}} \cdot i(G,N[v]^-).
\end{equation*}
\notag
$$
Имеют место равенства
$$
\begin{equation*}
i(G,v^+_{j},V^-_j)=i(G \setminus (N[v] \cup N[v_j])), \qquad i(G,N[v]^-)=i(G \setminus N[v]).
\end{equation*}
\notag
$$
Кроме того, граф $G \setminus (N[v] \cup N[v_j])$ является порожденным подграфом графа $G \setminus N[v]$, содержащим не менее ${|V(G \setminus N[v])| - d_j+ 1}$ вершин. Обозначим через $G'$ граф, полученный из графа $G \setminus N[v]$ удалением всех ребер, не принадлежащих подграфу $G \setminus (N[v] \cup N[v_j])$. Из (3.11) следует, что при удалении ребра из графа количество его НМ не уменьшается, тогда
$$
\begin{equation*}
2^{d_j-1} \cdot i(G \setminus (N[v] \cup N[v_j])) \geqslant i(G') \geqslant i(G \setminus N[v]).
\end{equation*}
\notag
$$
Лемма доказана. Лемма 8. При всех $m \geqslant 1$ для любого $2m$-вершинного субкубического графа $G$ имеет место неравенство $i(G) \geqslant 2^m$. Доказательство. Применим индукцию по $m$; база $m \leqslant 2$ очевидна. Если $G \cong 2mK_1$, то $i(G)=2^{2m}$ и доказывать нечего. Иначе рассмотрим некоторые вершины $u,v \in V(G)$, соединенные ребром. Поскольку $i(G,u^+,v^+)=0$, то Ясно, что граф $G \setminus \{u,v\}$ является $(2m-2)$-вершинным субкубическим, тогда $i(G,u^-,v^-) \geqslant 2^{m-1}$. Графы $G \setminus N[u]$ и $G \setminus N[v]$ являются субкубическими и содержат не менее $2m-4$ вершин каждый; тогда имеет место неравенство $\min\{i(G,u^-,v^+),i(G,u^+,v^-)\}\geqslant 2^{m-2}$, откуда следует утверждение леммы. 3.3. Лемма об изолированных вершинахСледующий простой факт будет часто использоваться при доказательстве основного результата работы. Лемма 9. Пусть для графа $G$ без висячих вершин выполнено $\overline{d}(G) \leqslant 2$. Граф $G'$ получается из графа $G$ удалением $p \geqslant 0$ вершин и $p+q \geqslant 1$ ребер, при этом каждая компонента связности $G'$ содержит не более одной висячей вершины. Тогда $G'$ содержит не менее $q$ изолированных вершин. Доказательство. По условию каждая компонента связности $H'$ графа $G'$, содержащая хотя бы одно ребро, содержит не более одной висячей вершины; тогда $H'$ не дерево и $\overline{d}(H') \geqslant 2$. Удалим из $G'$ все его компоненты связности, содержащие ребра, и обозначим через $G^*$ полученный граф. Поскольку $\overline{d}(G) \leqslant 2$, то $|V(G)| \geqslant |E(G)|$, откуда получаем $|V(G')| \geqslant |E(G')|+q$ и $|V(G^*)| \geqslant |E(G^*)|+q$. Таким образом, $G^* \cong q'K_1$, где $q' \geqslant q$. Поскольку $G'$ содержит $G^*$ в качестве подграфа, то условие леммы выполнено.
Лемма доказана. § 4. Основной результат Доказательство. Легко проверить, что утверждение выполнено для всех $n$-вершинных графов при $n \leqslant 3$. Рассмотрим нерегулярный граф $G$ с наименьшим количеством вершин, для которого верно $\overline{d}(G) \leqslant 1$ и $i(G) \leqslant \partial_1(G)$. Ясно, что $G$ содержит хотя бы одну изолированную вершину. Пусть такая вершина единственна. Так как $\overline{d}(G) \leqslant 1$, то $G$ содержит не более одной вершины степени более 1, причем если такая вершина присутствует, то она имеет степень 2. Тогда $G \cong aP_3 \cup bK_2 \cup K_1$ для некоторых $a \in \{0,1\}$ и $b \geqslant 0$, откуда получаем $\partial_1(G)=5^a \cdot 3^b < 2 \cdot 5^a \cdot 3^b=i(G)$; противоречие.
Пусть теперь $G$ содержит хотя бы две изолированные вершины. Выберем ребро $uv \in E(G)$ таким образом, чтобы вершина $u$ имела минимальную степень среди всех неизолированных вершин $G$ (если такой вершины нет, то $G$ не содержит ребер и доказывать нечего). Рассмотрим граф $G'$, полученный из $G$ удалением двух изолированных вершин, а также ребра $uv$. Поскольку $\overline{d}(G) \leqslant 1$, то $\overline{d}(G') \leqslant 1$ и $\partial_1(G') \leqslant i(G')$ по предположению. При этом ребро $uv$ было выбрано таким образом, что вершина $u$ либо является изолированной в $G'$, либо смежна в $G'$ хотя бы с одной вершиной степени не менее 2; тогда граф $G'$ не является 1-регулярным и $\partial_1(G') < i(G')$. Из (3.11) следует неравенство $i(G) \geqslant 3 \cdot i(G')$. Покажем, что $\partial_1(G) \leqslant 3 \cdot \partial_1(G')$. Имеем
$$
\begin{equation*}
\begin{aligned} \, 3 \cdot \partial_1(G') &\stackrel{{(3.1)}}{\geqslant} 3 \cdot (\partial_1(G',u^+,v^+)+\partial_1(G',u^-,v^-)) \\ &\,\,=3 \cdot (\partial_1(G,u^+,v^+)+\partial_1(G,u^-,v^-)) \\ &\stackrel{{(3.7)}}{\geqslant} \partial_1(G,u^+,v^+)+ \partial_1(G,u^+,v^-)+\partial_1(G,u^-,v^+)+\partial_1(G,u^-,v^-) \\ &\,\,= \partial_1(G). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, $\partial_1(G) < i(G)$; противоречие. Теорема доказана. Доказательство. Легко проверить, что утверждение выполнено для всех $n$-вершинных графов при $n \leqslant 3$. Рассмотрим нерегулярный граф $G$ с наименьшим количеством вершин, для которого верно $\overline{d}(G) \leqslant 2$ и $i(G) \leqslant \partial_2(G)$. Напомним, что условие $\overline{d}(G) \leqslant 2$ эквивалентно неравенству $|V(G)| \geqslant |E(G)|$. Всюду в тексте доказательства через $G_m$ обозначается граф, полученный удалением $m \geqslant 1$ вершин и такого же количества ребер из $G$, а через $G'_m$ обозначается граф, полученный удалением $m \geqslant 1$ вершин и $m' \geqslant m$ ребер из $G$.
Доказательство теоремы состоит из рассмотрения следующих 10 случаев. Случай 1: $G$ содержит хотя бы одну висячую вершину. Случай 2: $G$ содержит хотя бы одну 2-регулярную компоненту связности. Случай 3: $G$ содержит хотя бы одну 3-регулярную компоненту связности. Случай 4: $G$ содержит хотя бы две смежные вершины $u$ и $v$ степени не менее 4 каждая. Случай 5: $G$ содержит два треугольника, имеющих общее ребро, при этом все их вершины имеют степень не менее 3. Случай 6: $G$ содержит треугольник, не все вершины которого имеют степень 3. Случай 7: $G$ содержит треугольник, все вершины которого имеют степень 3, при этом хотя бы две из соседних с ними вершин имеют степень не менее 3. Случай 8: $G$ содержит треугольник, все вершины которого имеют степень 3, при этом хотя бы две из соседних с ними вершин имеют степень 2. Случай 9: $G$ содержит вершину степени не менее 3, которая смежна с вершиной степени 3 и не имеет с ней общих соседей. Случай 10: все вершины степени более 2 графа $G$ попарно несмежны. При рассмотрении каждого случая предполагается, что граф $G$ не удовлетворяет критериям ни одного из предыдущих случаев. В частности, имеются следующие предположения:
Перейдем к разбору случаев. В каждом из них мы доказываем неравенство $i(G) > \partial_2(G)$ и тем самым приходим к противоречию с предположением теоремы. Случай 1 ($G$ содержит хотя бы одну висячую вершину $u$). Обозначим через $v$ ее единственного соседа и рассмотрим два подслучая. Случай 1а: вершины $u$ и $v$ образуют компоненту связности $K_2$. Рассмотрим граф $G'=(G \setminus K_2) \cup K_1$. Поскольку $\overline{d}(G) \leqslant 2$, то $\overline{d}(G') \leqslant 2$ и по предположению $\partial_2(G') < i(G')$. Кроме того, $\partial_2(G)= \partial_2(G')$ и $i(G)=(3/2) \cdot i(G')$, откуда получаем $\partial_2(G) < i(G)$. Случай 1b: вершина $v$ смежна с вершинами $v_1,\dots, v_m$, отличными от $u$. Через $G_1$ обозначим результат удаления вершины $u$ из $G$, а через $G'_2$ – результат удаления вершины $v$ из $G_1$. Легко видеть, что $\overline{d}(G_1) \leqslant 2$ и $\overline{d}(G'_2) \leqslant 2$, откуда получаем $\partial_2(G_1) \leqslant i(G_1)$ и $\partial_2(G'_2) \leqslant i(G'_2)$ по предположению. Имеет место равенство
$$
\begin{equation*}
i(G) \stackrel{{(3.4)}}{=} i(G,u^-)+i(G,u^+)=i(G \setminus u )+i(G \setminus N[u])=i(G_1)+i(G'_2),
\end{equation*}
\notag
$$
тогда достаточно доказать, что $\partial_2(G) \leqslant \partial_2(G_1)+\partial_2(G'_2)$. Поскольку висячая вершина $u$ входит в каждое 2-ДМ графа $G$, то
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G) &=\partial_2(G,u^+) \stackrel{{(3.3)}}{=} \partial_2(G,u^+,v^+)+\partial_2(G,u^+,v^-) \\ &= \partial_2(G,v^+)+\partial_2(G \setminus \{u,v\})= \partial_2(G_1,v^+)+\partial_2(G'_2) \stackrel{{(3.5)}}{\leqslant} \partial_2(G_1)+\partial_2(G'_2). \end{aligned}
\end{equation*}
\notag
$$
Так как хотя бы один из графов $G_1$ и $G'_2$ не является 2-регулярным, то хотя бы одно из неравенств $\partial_2(G_1) \leqslant i(G_1)$ и $\partial_2(G'_2) \leqslant i(G'_2)$ является строгим, откуда следует строгое неравенство $\partial_2(G) < i(G)$. Случай 2 ($G$ содержит 2-регулярную компоненту связности, т.е. цикл $C_m$, где $m \geqslant 3$). Поскольку $\overline{d}(G \setminus C_m) \leqslant 2$ и граф $G$ не является 2-регулярным, то граф $G \setminus C_m$ также не является 2-регулярным. Так как $\partial_2(C_m)=i(C_m)$ и $\partial_2(G \setminus C_m) < i(G \setminus C_m)$, то получаем $\partial_2(G) < i(G)$, что и требовалось. Случай 3 ($G$ содержит 3-регулярную компоненту связности $H$). Считаем, что $H$ содержит $2m$ вершин и $3m$ ребер для некоторого $m \geqslant 2$. Мы предполагаем, что $G$ не содержит висячих вершин и $\overline{d}(G) \leqslant 2$. Тогда $|V(G)| \geqslant |E(G)|$, откуда получаем $|V(G \setminus H)| \geqslant |E(G \setminus H)|+m$. В графе $G \setminus H$ по-прежнему нет висячих вершин, тогда по лемме 9 в нем найдется не менее $m$ изолированных вершин. Обозначим через $G'$ результат удаления из $G$ подграфа $mK_1 \cup H$, тогда $|V(G')| \geqslant |E(G')|$ и $i(G') \geqslant \partial_2(G')$ по предположению. Покажем, что
$$
\begin{equation*}
i(mK_1 \cup H)= 2^m \cdot i(H) > \partial_2(H)=\partial_2(mK_1 \cup H).
\end{equation*}
\notag
$$
Действительно, неравенство $i(H) \geqslant 2^m$ выполнено по лемме 8, а неравенство $\partial_2(H) < 2^{2m}$ тривиально. Таким образом, $i(G) > \partial_2(G)$, что и требовалось. Случай 4 ($G$ содержит хотя бы две смежные вершины $u$ и $v$ степени не менее 4 каждая). Рассмотрим множества вершин $ N(u) \setminus \{v\}=\{u_1,\dots,u_p\}$ и $N(v) \setminus \{u\}= \{v_1,\dots,v_q\} $. Отметим, что данные множества могут пересекаться, на ход рассуждений это не влияет. Обозначим через $G_1$ результат удаления из $G$ ребра $uv$ и изолированной вершины. Поскольку $\operatorname{deg}_{G_1}(u) \geqslant 3$, то граф $G_1$ не 2-регулярен. При этом $\overline{d}(G_1) \leqslant 2$, тогда $\partial_2(G_1) < i(G_1)$. Из (3.11) следует, что при добавлении ребра в граф количество его НМ уменьшается не более чем в $4/3$ раз, тогда получаем $i(G) \geqslant 2 \cdot (3/4) \cdot i(G_1)$. Осталось доказать, что
$$
\begin{equation}
\partial_2(G) \leqslant \frac 32 \cdot \partial_2(G_1).
\end{equation}
\tag{4.1}
$$
Поскольку выполнены равенства
$$
\begin{equation*}
\begin{gathered} \, \partial_2(G) \stackrel{{(3.1)}}{=} \partial_2(G,u^+,v^+)+ \partial_2(G,u^+,v^-)+\partial_2(G,u^-,v^+)+\partial_2(G,u^-,v^-), \\ \partial_2(G,u^+,v^+)=\partial_2(G_1,u^+,v^+), \qquad \partial_2(G,u^-,v^-)=\partial_2(G_1,u^-,v^-), \end{gathered}
\end{equation*}
\notag
$$
то из (3.10) получаем соотношение
$$
\begin{equation*}
\partial_2(G)=\partial_2(G_1)+\partial_2^*(G,G_1,u^+,v^-)+ \partial_2^*(G,G_1,u^-,v^+).
\end{equation*}
\notag
$$
Тогда неравенство (4.1) следует из неравенства
$$
\begin{equation}
\begin{aligned} \, \notag &\partial_2^*(G,G_1,u^+,v^-)+\partial_2^*(G,G_1,u^-,v^+) \\ &\qquad \leqslant \frac 12 \cdot ( \partial_2(G_1,u^+,v^+)+\partial_2(G_1,u^+,v^-)+ \partial_2(G_1,u^-,v^+)). \end{aligned}
\end{equation}
\tag{4.2}
$$
Поскольку
$$
\begin{equation*}
\max\{\partial_2(G_1,u^+,v^-),\partial_2(G_1,u^-,v^+)\} \stackrel{{(3.7)}}{\leqslant} \partial_2(G_1,u^+,v^+),
\end{equation*}
\notag
$$
то достаточно доказать, что
$$
\begin{equation}
\partial^*_2(G,G_1,u^+,v^-) \leqslant \frac 34 \cdot \partial_2(G_1,u^+,v^-),
\end{equation}
\tag{4.3}
$$
$$
\begin{equation}
\partial^*_2(G,G_1,u^-,v^+) \leqslant \frac 34 \cdot \partial_2(G_1,u^-,v^+).
\end{equation}
\tag{4.4}
$$
Докажем неравенство (4.3). Рассмотрим два варианта в зависимости от значения величины $q$. Вариант $q=3$. Имеет место соотношение
$$
\begin{equation*}
\begin{aligned} \, \partial^*_2(G,G_1,u^+,v^-) &= \partial_2(G,u^+,v^-,v^+_1,v^-_{2},v^-_{3})+ \partial_2(G,u^+,v^-,v^-_{1},v^+_{2},v^-_{3}) \\ &\qquad+ \partial_2(G,u^+,v^-,v^-_{1},v^-_{2},v^+_{3}) \\ &\!\!\stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^+,v^-,v^+_{1},v^+_{2},v^-_{3})+ \partial_2(G,u^+,v^-,v^-_{1},v^+_{2},v^+_{3}) \\ &\qquad+ \partial_2(G,u^+,v^-,v^+_{1},v^-_{2},v^+_{3}) \\ &=\partial_2(G_1,u^+,v^-,v^+_{1},v^+_{2},v^-_{3})+ \partial_2(G_1,u^+,v^-,v^-_{1},v^+_{2},v^+_{3}) \\ &\qquad+ \partial_2(G_1,u^+,v^-,v^+_{1},v^-_{2},v^+_{3}) \\ &\!\!\stackrel{{(3.1)}}{\leqslant} \partial_2(G_1,u^+,v^-) - \partial_2(G_1,u^+,v^-,v^+_{1},v^+_{2},v^+_{3}) \\ &\!\!\stackrel{{(3.7)}}{\leqslant} \frac 34 \cdot \partial_2(G_1,u^+,v^-). \end{aligned}
\end{equation*}
\notag
$$
Вариант $q=4$. Положим
$$
\begin{equation*}
V_i=N_G(v) \setminus \{u,v_i\}, \qquad V_{i,j}=N_G(v) \setminus \{u,v_i,v_j\}
\end{equation*}
\notag
$$
(здесь $1 \leqslant i,j \leqslant q$ и $i \neq j$). Имеем
$$
\begin{equation*}
\begin{aligned} \, &2 \cdot \partial_2^*(G,G_1,u^+,v^-)=2 \cdot \sum_{i=1}^q \partial_2(G,u^+,v^-,v^+_{i},V_i^-) \\ &\qquad \stackrel{{(3.7), (3.9)}}{\leqslant} \biggl( \partial_2(G_1,u^+,v^-,v_1^+,v_q^+,V^-_{1,q})+\sum_{i=1}^{q-1} \partial_2(G_1,u^+,v^-,v^+_{i},v^+_{i+1},V^-_{i,j})\biggr) \\ &\qquad\qquad\qquad + \sum_{i=1}^q \partial_2(G_1,u^+,v^-,v^-_{i},V_i^+) \\ &\qquad\ \ \, \stackrel{{(3.1)}}{<} \partial_2(G_1,u^+,v^-). \end{aligned}
\end{equation*}
\notag
$$
Неравенство (4.3) доказано. Легко видеть, что неравенство (4.4) доказывается аналогично, откуда следует (4.2), что и требовалось. Случай 5 ($G$ содержит треугольники $abd$ и $bcd$, имеющие общее ребро $bd$, при этом $\operatorname{deg}(a),\operatorname{deg}(c) \geqslant 3$). Обозначим через $H$ подграф, порожденный вершинами этих треугольников. Возможны два случая. Случай 5а: $ac \in E(G)$, тогда $H \cong K_4$. Считаем, что только одна вершина $H$ (например, $a$) может быть смежна с вершинами из $G \setminus H$ (иначе в $H$ найдутся две смежные вершины, имеющие степень не менее 4 в $G$, этот случай уже рассмотрен ранее). Обозначим через $G'_3$ результат удаления вершин $b,c,d$ из $G$. Ясно, что ${|V(G'_3)| \geqslant |E(G'_3)| - 3}$ и $G'_3$ не содержит висячих вершин (кроме, быть может, вершины $a$). По лемме 9 граф $G'_3$ содержит хотя бы три изолированные вершины. Обозначим через $G_6$ результат удаления этих вершин из $G'_3$, при этом $\overline{d}(G_6) \leqslant 2$ и $i(G_6) \geqslant \partial_2(G_6)$ по предположению. Тогда
$$
\begin{equation*}
i(G) =8 \cdot (i(G_6,a^+)+4 \cdot i(G_6,a^-)) \stackrel{{(3.8)}}{\geqslant} 8 \cdot \frac{5}{2} \cdot (i(G_6,a^+)+ i(G_6,a^-))=20 \cdot i(G_6).
\end{equation*}
\notag
$$
По лемме 4 $\partial_2(G \setminus H) \leqslant \partial_2(3K_1 \cup G_6)=\partial_2(G_6)$, тогда получаем
$$
\begin{equation*}
\partial_2(G)=\partial_2(G,a^+)+\partial_2(G,a^-)=7 \cdot \partial_2(G_6,a^+)+4 \cdot \partial_2(G \setminus H) \leqslant 11 \cdot \partial_2(G_6) < i(G),
\end{equation*}
\notag
$$
что и требовалось. Случай 5b: $ac \notin E(G)$, тогда $H \cong K_4 - e$. Считаем, что $\operatorname{deg}(b) \geqslant \operatorname{deg}(d)$. Мы предполагаем, что $G$ не содержит смежных вершин степени более 3, тогда $\operatorname{deg}(d)=3$. Поскольку $\operatorname{deg}(a), \operatorname{deg}(c) \geqslant 3$ по предположению, то граф $G \setminus d$ не содержит висячих вершин. Тогда по лемме 9 он содержит хотя бы две изолированные вершины. Обозначим через $G_3$ результат удаления этих вершин из $G \setminus d$. Из $(3.2)$ и $(3.8)$ следует неравенство $i(G_3) \leqslant 8 \cdot i(G_3,a^-,b^-,c^-)$, тогда получаем
$$
\begin{equation*}
\begin{aligned} \, i(G) &\stackrel{{(3.4)}}{=} i(G,d^-)+i(G,d^+)=i(2K_1) \cdot (i(G_3)+i(G_3,a^-,b^-,c^-)) \\ &\ \, \geqslant 4 \cdot (i(G_3)+\frac 18 \cdot i(G_3))=\frac 92 \cdot i(G_3). \end{aligned}
\end{equation*}
\notag
$$
Покажем, что $\partial_2(G) < (9/2) \cdot \partial_2(G_3)$. Разобьем доказательство на три шага. Шаг 1. Применяя $(3.3)$, имеем
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G,a^+,b^+,c^+) &=\partial_2(G,a^+,b^+,c^+,d^-)+ \partial_2(G,a^+,b^+,c^+,d^+) \\ &= 2 \cdot \partial_2(G_3,a^+,b^+,c^+). \end{aligned}
\end{equation*}
\notag
$$
Аналогично,
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G,a^+,b^-,c^+) &=\partial_2(G,a^+,b^-,c^+,d^-)+ \partial_2(G,a^+,b^-,c^+,d^+) \\ &= 2 \cdot \partial_2(G_3,a^+,b^-,c^+). \end{aligned}
\end{equation*}
\notag
$$
Шаг 2. Имеем
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G,a^+,b^+,c^-) &\stackrel{{(3.3)}}{=} \partial_2(G,a^+,b^+,c^-,d^+)+\partial_2(G,a^+,b^+,c^-,d^-) \\ &\stackrel{{(3.7)}}{\leqslant} \partial_2(G,a^+,b^+,c^+,d^+)+ \partial_2(G,a^+,b^+,c^-,d^-) \\ &\stackrel{{(3.5)}}{\leqslant} \partial_2(G_3,a^+,b^+,c^+)+ \partial_2(G_3,a^+,b^+,c^-). \end{aligned}
\end{equation*}
\notag
$$
Аналогично,
$$
\begin{equation*}
\partial_2(G,a^-,b^+,c^+) \leqslant \partial_2(G_3,a^+,b^+,c^+)+\partial_2(G_3,a^-,b^+,c^+).
\end{equation*}
\notag
$$
Поскольку каждое 2-ДМ графа $G$, содержащее не более одной вершины множества $\{a,b,c\}=N_G(d)$, содержит вершину $d$, то
$$
\begin{equation*}
\begin{gathered} \, \partial_2(G,a^+,b^-,c^-)=\partial_2(G,a^+,b^-,c^-,d^+) \leqslant \partial_2(G_3,a^+,b^+,c^-), \\ \partial_2(G,a^-,b^-,c^+)= \partial_2(G,a^-,b^-,c^+,d^+) \leqslant \partial_2(G_3,a^-,b^+,c^+), \\ \partial_2(G,a^-,b^-,c^-)=\partial_2(G,a^-,b^-,c^-,d^+) \leqslant \partial_2(G_3,a^-,b^+,c^-). \end{gathered}
\end{equation*}
\notag
$$
Шаг 3. Докажем, что $\partial_2(G,a^-,b^+,c^-) \leqslant 2 \cdot \partial_2(G_3,a^+,b^+,c^-)$. Положим $C=N_G(c) \setminus \{b,d\}$. Поскольку $\operatorname{deg}_G(c) \geqslant 3$, то множество $C$ непусто. Тогда получаем
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G,a^-,b^+,c^-) &=\partial_2(G,a^-,b^+,c^-,d^+) \stackrel{{(3.7)}}{\leqslant} \partial_2(G,a^+,b^+,c^-,d^+) \\ &= \partial_2(G_3,a^+,b^+,c^-)+\partial_2(G,a^+,b^+,c^-,C^-,d^+) \\ &\!\!\stackrel{{(3.9)}}{\leqslant} \partial_2(G_3,a^+,b^+,c^-) + \partial_2(G,a^+,b^+,c^-,C^+,d^-) \\ &= \partial_2(G_3,a^+,b^+,c^-) + \partial_2(G_3,a^+,b^+,c^-,C^+) \\ &\!\! \stackrel{{(3.5)}}{\leqslant} 2 \cdot \partial_2(G_3,a^+,b^+,c^-). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, мы доказали, что
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G) &\leqslant 4 \cdot \partial_2(G_3,a^+,b^+,c^+)+4 \cdot \partial_2(G_3,a^+,b^+,c^-)+2 \cdot \partial_2(G_3,a^-,b^+,c^+) \\ &\qquad+2 \cdot \partial_2(G_3,a^+,b^-,c^+)+\partial_2(G_3,a^-,b^+,c^-) \\ &< \frac 92 \cdot \partial_2(G_3) \leqslant \frac 92 \cdot i(G_3) \leqslant i(G). \end{aligned}
\end{equation*}
\notag
$$
Случай 6 (граф $G$ содержит треугольник $uvw$, не все вершины которого имеют степень 3). Случай 6a: хотя бы две вершины треугольника (например, $v$ и $w$) имеют степень 2. Мы предполагаем, что $G$ не содержит 2-регулярных подграфов, тогда $\operatorname{deg}(u) \geqslant 3$. Удалим из $G$ вершины $v$ и $w$ и изолированную вершину, обозначим через $G_3$ полученный граф. Ясно, что если $\overline{d}(G) \leqslant 2$, то и $\overline{d}(G_3) \leqslant 2$. Поскольку $\operatorname{deg}_{G_3}(u) \geqslant 1$, то из (3.12) следует неравенство $i(G_3,u^+) < i(G_3,u^-)$, откуда получаем
$$
\begin{equation*}
i(G)=2 \cdot (i(G_3,u^+)+3 \cdot i(G_3,u^-)) > 4 \cdot i(G_3).
\end{equation*}
\notag
$$
По лемме 4 $\partial_2(G_3) \geqslant \partial_2(G_3 \setminus u)$. Каждое 2-ДМ $D' \in \mathfrak{D}_2(G,u^+)$ содержит хотя бы одну вершину из множества $\{v,w\}$, а каждое 2-ДМ $D'' \in \mathfrak{D}_2(G,u^-)$ содержит обе эти вершины, тогда получаем
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G) &\stackrel{{(3.1)}}{=} \partial_2(G,u^+,v^+,w^+)+\partial_2(G,u^+,v^+,w^-) \\ &\qquad\ + \partial_2(G,u^+,v^-,w^+) + \partial_2(G,u^-,v^+,w^+) \\ &\ =3 \cdot \partial_2(G_3,u^+)+ \partial_2(G_3 \setminus u) \leqslant 4 \cdot \partial_2(G_3) < i(G). \end{aligned}
\end{equation*}
\notag
$$
Случай 6b: ровно одна вершина треугольника (например, вершина $w$) имеет степень 2. Обозначим через $G_1$ граф, полученный удалением из $G$ ребра $uv$ и изолированной вершины. Поскольку $N_{G_1}(w)=\{u,v\}$, то получаем
$$
\begin{equation*}
i(G_1,u^-,v^-) \stackrel{{(3.4)}}{=} i(G_1,u^-,v^-,w^-)+ i(G_1,u^-,v^-,w^+) \geqslant 2 \cdot i(G_1,u^+,v^+).
\end{equation*}
\notag
$$
Из (3.8) следует, что $\min\{i(G_1,u^-,v^+),i(G_1,u^+,v^-)\}\geqslant i(G_1,u^+,v^+)$, тогда
$$
\begin{equation}
4 \cdot i(G_1,u^+,v^+) \leqslant i(G_1,u^-,v^+)+i(G_1,u^+,v^-)+ i(G_1,u^-,v^-).
\end{equation}
\tag{4.5}
$$
Следовательно,
$$
\begin{equation*}
\frac{i(G)}{i(G_1)} \geqslant 2 \cdot \frac{i(G_1,u^-,v^+)+i(G_1,u^+,v^-)+ i(G_1,u^-,v^-)}{i(G_1,u^+,v^+)+i(G_1,u^-,v^+)+i(G_1,u^+,v^-)+ i(G_1,u^-,v^-)} \geqslant \frac 85.
\end{equation*}
\notag
$$
Покажем, что $\partial_2(G) \leqslant (8/5) \cdot \partial_2(G_1)$. Как следует из рассуждений случая 4, для этого нам достаточно доказать соотношение
$$
\begin{equation}
\begin{aligned} \, \notag &\partial^*_2(G,G_1,u^-,v^+)+\partial^*_2(G,G_1,u^+,v^-) \\ &\qquad \leqslant \frac 35 \cdot (\partial_2(G_1,u^+,v^+)+\partial_2(G_1,u^-,v^+)+ \partial_2(G_1,u^+,v^-)+\partial_2(G_1,u^-,v^-)). \end{aligned}
\end{equation}
\tag{4.6}
$$
Докажем неравенство
$$
\begin{equation}
5 \cdot \partial^*_2(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^+,v^+)+ 3 \cdot \partial_2(G_1,u^-,v^+).
\end{equation}
\tag{4.7}
$$
Покажем, что
$$
\begin{equation}
2 \cdot \partial^*_2(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.8}
$$
Введем обозначение $U=N_G(u) \setminus \{v,w\}$. Каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^-)$ содержит вершину $w$. Так как $\operatorname{deg}(w)=2$, то $\partial_2(G,u^+,v^+,w^+)=\partial_2(G,u^+,v^+,w^-)$, тогда получаем
$$
\begin{equation*}
\begin{aligned} \, & 2 \cdot \partial^*_2(G,G_1,u^-,v^+)=2 \cdot \partial^*_2(G,G_1,u^-,v^+,w^+)=2 \cdot \partial_2(G,u^-,U^-,v^+,w^+) \\ &\qquad \stackrel{{(3.5), (3.7)}}{\leqslant} 2 \cdot \partial_2(G,u^+,v^+,w^+)=\partial_2(G,u^+,v^+,w^-)+ \partial_2(G,u^+,v^+,w^+) \\ &\qquad\quad\ =\partial_2(G_1,u^+,v^+,w^-)+\partial_2(G_1,u^+,v^+,w^+) \stackrel{{(3.3)}}{=} \partial_2(G_1,u^+,v^+). \end{aligned}
\end{equation*}
\notag
$$
Теперь покажем, что
$$
\begin{equation}
\partial^*_2(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^-,v^+).
\end{equation}
\tag{4.9}
$$
Имеем
$$
\begin{equation*}
\begin{aligned} \, \partial^*_2(G,G_1,u^-,v^+) &=\partial_2(G,u^-,U^-,v^+,w^+) \stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^-,U^+,v^+,w^+) \\ & = \partial_2(G_1,u^-,U^+,v^+,w^+) \stackrel{{(3.5)}}{\leqslant} \partial_2(G_1,u^-,v^+). \end{aligned}
\end{equation*}
\notag
$$
Из неравенств (4.8) и (4.9) вытекает (4.7). Аналогичным образом доказывается неравенство
$$
\begin{equation*}
5 \cdot \partial^*_2(G,G_1,u^+,v^-) \leqslant \partial_2(G_1,u^+,v^+)+3 \cdot \partial_2(G_1,u^+,v^-),
\end{equation*}
\notag
$$
откуда следует (4.6), что и требовалось. Случай 6c: хотя бы одна вершина треугольника (например, вершина $u$) имеет степень не менее 4. Мы предполагаем, что $\operatorname{deg}(v)=\operatorname{deg}(w)=3$ (иное уже было разобрано в случаях 4, 6a и 6b). Обозначим через $u_1,\dots,u_m$ соседей $u$, а через $v_1$ и $w_1$ единственных соседей $v$ и $w$ вне треугольника $uvw$ соответственно. Мы предполагаем, что $G$ не содержит двух треугольников с общим ребром (так как это было уже разобрано в случаях 5 и 6b). Следовательно, вершины $u_1,\dots,u_m,v_1,w_1$ попарно различны. Обозначим через $G_1$ результат удаления из $G$ ребра $uv$ и изолированной вершины. Покажем, что $i(G) \geqslant (8 / 5) \cdot i(G_1)$. Как и в случае 6b, для этого достаточно доказать неравенство (4.5). В графе $G \setminus v$ вершина $w$ имеет степень 2, а остальные соседи $u$ имеют степень не более 3, тогда из (3.12) следует неравенство $i(G_1,u^-,v^-) \geqslant 2 \cdot i(G_1,u^+,v^-)$. Кроме того, из (3.8) следует неравенство
$$
\begin{equation*}
\min\{i(G_1,u^+,v^-),i(G_1,u^-,v^+)\} \geqslant i(G_1,u^+,v^+),
\end{equation*}
\notag
$$
откуда получаем $i(G) \geqslant (8 / 5) \cdot i(G_1)$. Теперь покажем, что $\partial_2(G) \leqslant (8 / 5) \cdot \partial_2(G_1)$. Как и в случае 6b, для этого достаточно доказать неравенство (4.6). Разобьем доказательство на два шага. Шаг 1. Покажем, что
$$
\begin{equation}
5 \cdot \partial_2^*(G,G_1,u^-,v^+) \leqslant 3 \cdot \partial_2(G_1,u^-,v^+)+3 \cdot \partial_2(G_1,u^-,v^-)+\frac 12 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.10}
$$
Введем обозначения $U=N(u) \setminus \{v,w\}$ и $U_i=U \setminus \{u_i\}$, $1 \leqslant i \leqslant m$. Тогда неравенство
$$
\begin{equation}
\partial_2^*(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^-,v^+)
\end{equation}
\tag{4.11}
$$
следует из соотношений
$$
\begin{equation*}
\begin{aligned} \, &\partial_2^*(G,G_1,u^-,v^+) =\partial_2^*(G,G_1,u^-,v^+,w^+)+ \partial_2^*(G,G_1,u^-,v^+,w^-) \\ &\qquad=\partial_2(G,u^-,U^-,v^+,w^+)+\sum_{i=1}^m \partial_2(G,u^-,u^+_{i},U^-_i,v^+,w^-) \\ &\!\!\!\!\!\!\!\qquad\stackrel{{(3.7), (3.9)}}{\leqslant} \partial_2(G_1,u^-,U^+,v^+,w^+)+\sum_{i=1}^m \partial_2(G_1,u^-,u^-_{i},U^+_i,v^+,w^+) \\ &\!\qquad\stackrel{{(3.1)}}{\leqslant} \partial_2(G_1,u^-,v^+). \end{aligned}
\end{equation*}
\notag
$$
Теперь докажем, что
$$
\begin{equation}
\partial_2^*(G,G_1,u^-,v^+) \leqslant 2 \cdot \partial_2(G,u^-,v^-).
\end{equation}
\tag{4.12}
$$
Имеем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2^*(G,G_1,u^-,v^+) =\partial_2(G,u^-,U^-,v^+,w^+)+ \sum_{i=1}^m \partial_2(G,u^-,u^+_{i},U^-_i,v^+,w^-) \\ &\!\!\!\!\!\!\!\qquad\stackrel{{(3.3), (3.7)}}{\leqslant} 2 \cdot \biggl( \partial_2(G,u^-,U^+,v^+,v^+_1,w^+)+ \sum_{i=1}^m \partial_2(G,u^-,u^+_{i},U^-_i,v^+,v^+_1,w^+)\biggr) \\ &\qquad= 2 \cdot \biggl(\partial_2(G_1,u^-,U^+,v^+,v^+_{1},w^+)+\sum_{i=1}^m \partial_2(G_1,u^-,u^+_{i},U^-_i,v^+,v^+_1,w^+)\biggr) \\ &\qquad= 2 \cdot \biggl(\partial_2(G_1,u^-,U^+,v^-,v^+_{1},w^+)+\sum_{i=1}^m \partial_2(G_1,u^-,u^+_{i},U^-_i,v^-,v^+_1,w^+)\biggr) \\ &\!\qquad\stackrel{{(3.1)}}{\leqslant} 2 \cdot \partial_2(G_1,u^-,v^-). \end{aligned}
\end{equation*}
\notag
$$
Наконец, из (3.7) следует, что $\partial_2(G,u^-,v^+) \leqslant \partial_2(G,u^+,v^+)$, откуда получаем
$$
\begin{equation}
\partial_2^*(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.13}
$$
Из неравенств (4.11)–(4.13) слудует неравенство (4.10), что и требовалось. Шаг 2. Покажем, что
$$
\begin{equation}
5 \cdot \partial_2^*(G,G_1,u^+,v^-) \leqslant 3 \cdot \partial_2(G_1,u^+,v^-)+\frac 52 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.14}
$$
Действительно,
$$
\begin{equation}
\begin{aligned} \, \notag \partial_2^*(G,G_1,u^+,v^-) &=\partial_2(G,u^+,v^-,w^+,v^-_{1})+ \partial_2(G,u^+,v^-,w^-,v^+_{1}) \\ \notag &\!\!\stackrel{{(3.7)}}{\leqslant} \frac 23 \cdot (\partial_2(G,u^+,v^+,w^+,v^-_{1}) +\partial_2(G,u^+,v^+,w^-,v^+_{1}) \\ &\qquad+\partial_2(G,u^+,v^+,w^+,v^+_{1})) \notag \\ \notag &= \frac 23 \cdot (\partial_2(G_1,u^+,v^+,w^+,v^-_{1}) +\partial_2(G_1,u^+,v^+,w^-,v^+_{1}) \\ &\qquad+\partial_2(G_1,u^+,v^+,w^+,v^+_{1})) \notag \\ &\!\!\stackrel{{(3.1)}}{\leqslant} \frac 23 \cdot \partial_2(G_1,u^+,v^+). \end{aligned}
\end{equation}
\tag{4.15}
$$
Кроме того,
$$
\begin{equation}
\begin{aligned} \, \notag \partial_2^*(G,G_1,u^+,v^-) &=\partial_2(G,u^+,v^-,w^+,v^-_{1})+ \partial_2(G,u^+,v^-,w^-,v^+_{1}) \\ \notag &\stackrel{{(3.7)}}{\leqslant} 2 \cdot \partial_2(G,u^+,v^-,w^+,v^+_{1})= 2 \cdot \partial_2(G_1,u^+,v^-,w^+,v^+_{1}) \\ &\stackrel{{(3.5)}}{\leqslant} 2 \cdot \partial_2(G_1,u^+,v^-). \end{aligned}
\end{equation}
\tag{4.16}
$$
Таким образом, из неравенств (4.15) и (4.16) следует неравенство (4.14), откуда получаем $\partial_2(G) \leqslant (8 / 5) \cdot \partial_2(G_1)$, что и требовалось. Случай 7 ($G$ содержит треугольник $uvw$, все вершины которого имеют степень 3, при этом хотя бы две из соседних вершин $u_1$, $v_1$ и $w_1$ – считаем, что это $u_1$ и $v_1$ – имеют степень не менее 3). Рассмотрим граф $G'_3$, полученный удалением из графа $G$ вершин $u$, $v$ и $w$. Все вершины $G'_3$, кроме, быть может, вершины $w_1$, не являются висячими. Значит, по лемме 9 граф $G'_3$ содержит хотя бы три изолированные вершины. Обозначим через $G_6$ граф, полученный в результате удаления этих вершин из $G'_3$. Тогда $\overline{d}(G_6) \leqslant 2$ и из соотношения (3.2) следуют равенства
$$
\begin{equation*}
\begin{aligned} \, i(G_6) &=i(G_6,u^+_1,v^+_1,w^+_1)+i(G_6,u^-_1,v^-_1,w^-_1) \\ &\qquad + i(G_6,u^+_1,v^+_1,w^-_1)+i(G_6,u^+_1,v^-_1,w^+_1)+ i(G_6,u^-_1,v^+_1,w^+_1) \\ &\qquad+ i(G_6,u^-_1,v^-_1,w^+_1)+ i(G_6,u^-_1,v^+_1,w^-_1)+ i(G_6,u^+_1,v^-_1,w^-_1), \\ \frac 18 \cdot i(G) &=i(G_6,u^+_1,v^+_1,w^+_1)+4 \cdot i(G_6,u^-_1,v^-_1,w^-_1) \\ &\qquad+ 2 \cdot (i(G_6,u^+_1,v^+_1,w^-_1)+i(G_6,u^+_1,v^-_1,w^+_1)+ i(G_6,u^-_1,v^+_1,w^+_1)) \\ &\qquad + 3 \cdot (i(G_6,u^-_1,v^-_1,w^+_1)+ i(G_6,u^-_1,v^+_1,w^-_1)+ i(G_6,u^+_1,v^-_1,w^-_1)). \end{aligned}
\end{equation*}
\notag
$$
Из (3.8) следуют неравенства
$$
\begin{equation*}
\begin{gathered} \, i(G_6,u^+_1,v^+_1,w^+_1) \leqslant i(G_6,u^-_1,v^-_1,w^-_1), \\ \begin{aligned} \, &i(G_6,u^+_1,v^+_1,w^-_1)+i(G_6,u^+_1,v^-_1,w^+_1)+ i(G_6,u^-_1,v^+_1,w^+_1) \\ &\qquad \leqslant i(G_6,u^-_1,v^+_1,w^-_1)+ i(G_6,u^+_1,v^-_1,w^-_1)+ i(G_6,u^-_1,v^-_1,w^+_1), \end{aligned} \end{gathered}
\end{equation*}
\notag
$$
тогда получаем $i(G) \geqslant 20 \cdot i(G_6)$. Докажем, что $\partial_2(G) < 20 \cdot \partial_2(G_6)$. Рассмотрим два подслучая в зависимости от значения величины $\operatorname{deg}(w_1)$. Случай 7a: $\operatorname{deg}(w_1)=2$. Разобьем доказательство на три шага. Шаг 1. Поскольку каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^+_1,v^+_1,w^+_1)$ содержит хотя бы одну вершину из множества $\{u,v,w\}$, то
$$
\begin{equation*}
\partial_2(G,u^+_1,v^+_1,w^+_1)=7 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1).
\end{equation*}
\notag
$$
Поскольку $\operatorname{deg}(w_1)=2$, то каждое 2-ДМ $D' \in \mathfrak{D}_2(G,u^+_1,v^+_1,w^-_1)$ содержит $w$, откуда получаем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^+_1,v^+_1,w^-_1) \\ &\qquad \stackrel{{(3.1)}}{=} \partial_2(G,u^+_1,v^+_1,w^-_1,u^+,v^+,w^+)+ \partial_2(G,u^+_1,v^+_1,w^-_1,u^-,v^+,w^+) \\ &\qquad\qquad + \partial_2(G,u^+_1,v^+_1,w^-_1,u^+,v^-,w^+)+ \partial_2(G,u^+_1,v^+_1,w^-_1,u^-,v^-,w^+) \\ &\qquad\stackrel{{(3.7)}}{\leqslant} 4 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Шаг 2. Покажем, что $\partial_2(G,u^-_1,v^+_1,w^+_1) \leqslant 13 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1).$ Так как каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^-,u^-_1)$ содержит вершины $v$ и $w$, то получаем
$$
\begin{equation}
\begin{aligned} \, \notag \partial_2(G,u^-_1,v^+_1,w^+_1) &\stackrel{{(3.3)}}{=} \partial_2(G,u^-,v^+,w^+,u^-_1,v^+_1,w^+_1)+ \partial_2(G,u^+,u^-_1,v^+_1,w^+_1) \\ &\ \, = \partial_2(G_6,u^-_1,v^+_1,w^+_1)+4 \cdot \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1). \end{aligned}
\end{equation}
\tag{4.17}
$$
Рассмотрим три варианта в зависимости от того, смежна ли вершина $u_1$ с вершинами $v_1$ и $w_1$. Вариант 1: вершина $u_1$ смежна как с $v_1$, так и с $w_1$, тогда, очевидно,
$$
\begin{equation*}
\partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1)= \partial_2(G_6,u^-_1,v^+_1,w^+_1).
\end{equation*}
\notag
$$
Таким образом, из (4.17) следует $\partial_2(G,u^-_1,v^+_1,w^+_1) \leqslant 5 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1)$. Вариант 2: вершина $u_1$ смежна ровно с одной из вершин $v_1$ и $w_1$. Положим $U_1=N(u_1) \setminus \{u,v_1,w_1\}$. Поскольку $\operatorname{deg}_{G}(u_1) \geqslant 3$, то $U_1 \neq \varnothing$. Тогда получаем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1) \\ &\qquad = \partial_2(G_6,u^-_1,v^+_1,w^+_1)+ \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,U_1^-) \\ &\!\!\qquad \stackrel{{(3.7)}}{\leqslant} \partial_2(G_6,u^-_1,v^+_1,w^+_1)+ \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,U_1^+) \\ &\qquad\leqslant 2 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, из (4.17) следует $\partial_2(G,u^-_1,v^+_1,w^+_1) \leqslant 9 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1)$. Вариант 3: вершина $u_1$ не смежна с вершинами $v_1$ и $w_1$. Обозначим через $x_1,\dots,x_s$ соседей вершины $u_1$, отличных от $u$ (здесь $s \geqslant 2$ по предположению). Положим $X=N(u_1) \setminus u$ и $X_i=X \setminus x_i$, $1 \leqslant i \leqslant s$. Тогда имеет место равенство
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1) \\ &\qquad= \partial_2(G_6,u^-_1,v^+_1,w^+_1) + \sum_{i=1}^{s} \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,x^+_{i},X^-_i). \end{aligned}
\end{equation*}
\notag
$$
Если $\operatorname{deg}(u_1)=s+1=3$, то
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=1}^2 \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,x^+_{i},X^-_i) \\ &\!\!\qquad \stackrel{{(3.7)}}{\leqslant} 2 \cdot \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,X^+) \\ &\qquad= 2 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1,X^+) \stackrel{{(3.5)}}{\leqslant} 2 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Если же $\operatorname{deg}(u_1) \geqslant 4$, то
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=1}^{s} \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,x^+_{i},X^-_i) \\ &\!\!\qquad \stackrel{{(3.9)}}{\leqslant} \sum_{i=1}^{s} \partial_2(G,u^+,v^+,w^+,u^-_1,v^+_1,w^+_1,x^-_{i},X^+_i) \\ &\qquad = \sum_{i=1}^{s} \partial_2(G_6,u^-_1,v^+_1,w^+_1,x^-_{i},X^+_i) \stackrel{{(3.1)}}{<} \partial_2(G_6,u^-_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, из (4.17) следует
$$
\begin{equation*}
\partial_2(G,u^-_1,v^+_1,w^+_1) \leqslant 13 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1).
\end{equation*}
\notag
$$
Неравенство $\partial_2(G,u^+_1,v^-_1,w^+_1) \leqslant 13 \cdot \partial_2(G_6,u^+_1,v^-_1,w^+_1)$ доказывается аналогично. Шаг 3. Нетрудно видеть, что каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^+_1,v^-_1,w^-_1)$ содержит не менее двух вершин из множества $\{u,v,w\}$. Тогда имеет место неравенство
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^+_1,v^-_1,w^-_1) \\ &\qquad \stackrel{{(3.1)}}{=} \partial_2(G,u^+_1,v^-_1,w^-_1,u^+,v^+,w^+)+ \partial_2(G,u^+_1,v^-_1,w^-_1,u^-,v^+,w^+) \\ &\qquad\qquad + \partial_2(G,u^+_1,v^-_1,w^-_1,u^+,v^-,w^+)+ \partial_2(G,u^+_1,v^-_1,w^-_1,u^+,v^+,w^-) \\ &\qquad\stackrel{{(3.7)}}{\leqslant} 2 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+\partial_2(G_6,u^+_1,v^-_1,w^+_1)+ \partial_2(G_6,u^+_1,v^+_1,w^-_1). \end{aligned}
\end{equation*}
\notag
$$
Аналогично доказываются неравенства
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^-_1,v^+_1,w^-_1) \\ &\qquad\leqslant 2 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+\partial_2(G_6,u^-_1,v^+_1,w^+_1)+ \partial_2(G_6,u^+_1,v^+_1,w^-_1), \\ &\partial_2(G,u^-_1,v^-_1,w^+_1) \\ &\qquad\leqslant 2 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+\partial_2(G_6,u^-_1,v^+_1,w^+_1)+ \partial_2(G_6,u^+_1,v^-_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Из (3.7) следует неравенство $\partial_2(G,u^+_1,v^-_1,w^-_1) \geqslant \partial_2(G,u^-_1,v^-_1,w^-_1)$, тогда получаем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^-_1,v^-_1,w^-_1) \\ &\qquad\leqslant 2 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+\partial_2(G_6,u^+_1,v^-_1,w^+_1)+ \partial_2(G_6,u^+_1,v^+_1,w^-_1). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, мы доказали соотношение
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G) &\leqslant 19 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+15 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1) \\ &\qquad+ 16 \cdot \partial_2(G_6,u^+_1,v^-_1,w^+_1)+3 \cdot \partial_2(G_6,u^+_1,v^+_1,w^-_1) < 20 \cdot \partial_2(G_6). \end{aligned}
\end{equation*}
\notag
$$
Случай 7b: $\operatorname{deg}(w_1) \geqslant 3$. Разобьем доказательство на четыре шага. Шаг 1. Аналогично случаю 7a имеем
$$
\begin{equation*}
\partial_2(G,u_1^+,v_1^+,w_1^+)=7 \cdot \partial_2(G_6,u_1^+,v_1^+,w_1^+).
\end{equation*}
\notag
$$
Шаг 2. Так как $\min\{\operatorname{deg}(u_1),\operatorname{deg}(v_1),\operatorname{deg}(w_1)\}=3$, то рассуждения шага 2 случая 7a применимы к каждой из вершин $u_1$, $v_1$ и $w_1$. Таким образом,
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u_1^-,v_1^+,w_1^+)+\partial_2(G,u_1^+,v_1^-,w_1^+)+ \partial_2(G,u_1^+,v_1^+,w_1^-) \\ &\qquad \leqslant 13 \cdot (\partial_2(G_6,u_1^-,v_1^+,w_1^+) + \partial_2(G_6,u_1^+,v_1^-,w_1^+)+ \partial_2(G_6,u_1^+,v_1^+,w_1^-)). \end{aligned}
\end{equation*}
\notag
$$
Шаг 3. Докажем, что
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u_1^+,v_1^-,w_1^-)+\partial_2(G,u_1^-,v_1^+,w_1^-)+ \partial_2(G,u^-_1,v^-_1,w^+_1) \\ &\qquad \leqslant 12 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Не умаляя общности, будем считать, что
$$
\begin{equation*}
\partial_2(G,u_1^+,v_1^-,w_1^-)\,{=} \max\{\partial_2(G,u_1^+,v_1^-,w_1^-), \partial_2(G,u_1^-,v_1^+,w_1^-),\partial_2(G,u^-_1,v^-_1,w^+_1)\},
\end{equation*}
\notag
$$
тогда достаточно доказать неравенство
$$
\begin{equation*}
\partial_2(G,u^+_1,v^-_1,w^-_1) \leqslant 4 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1).
\end{equation*}
\notag
$$
Поскольку каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^+_1,v^-_1,w^-_1)$ содержит не менее двух вершин из множества $\{u,v,w\}$, то получаем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u^+_1,v^-_1,w^-_1) \\ &\qquad \stackrel{{(3.1)}}{=} \partial_2(G,u^+,v^+,w^+,u^+_1,v^-_1,w^-_1)+ \partial_2(G,u^+,v^+,w^-,u^+_1,v^-_1,w^-_1) \\ &\qquad\qquad + \partial_2(G,u^+,v^-,w^+,u^+_1,v^-_1,w^-_1)+ \partial_2(G,u^-,v^+,w^+,u^+_1,v^-_1,w^-_1) \\ &\qquad\stackrel{{(3.7)}}{\leqslant} 4 \cdot \partial_2(G,u^+,v^+,w^+,u^+_1,v^+_1,w^+_1) \leqslant 4 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1). \end{aligned}
\end{equation*}
\notag
$$
Шаг 4. Поскольку каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^-_1,v^-_1,w^-_1)$ также содержит не менее двух вершин из множества $\{u,v,w\}$, то получаем
$$
\begin{equation*}
\begin{aligned} \, &\partial_2(G,u_1^-,v_1^-,w_1^-) \\ &\qquad\stackrel{{(3.1)}}{=} \partial_2(G,u^+,v^+,w^+,u^-_1,v^-_1,w^-_1)+ \partial_2(G,u^+,v^+,w^-,u^-_1,v^-_1,w^-_1) \\ &\qquad\qquad + \partial_2(G,u^+,v^-,w^+,u^-_1,v^-_1,w^-_1)+ \partial_2(G,u^-,v^+,w^+,u^-_1,v^-_1,w^-_1) \\ &\qquad \stackrel{{(3.7)}}{\leqslant} \partial_2(G_6,u_1^+,v_1^+,w_1^+)+ \partial_2(G_6,u_1^+,v_1^+,w_1^-) \\ &\qquad\qquad + \partial_2(G_6,u_1^+,v_1^-,w_1^+)+ \partial_2(G_6,u_1^-,v_1^+,w_1^+). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, мы доказали соотношение
$$
\begin{equation*}
\begin{aligned} \, \partial_2(G) &\leqslant 20 \cdot \partial_2(G_6,u^+_1,v^+_1,w^+_1)+14 \cdot \partial_2(G_6,u^-_1,v^+_1,w^+_1) \\ &\qquad+ 14 \cdot \partial_2(G_6,u^+_1,v^-_1,w^+_1)+14 \cdot \partial_2(G_6,u^+_1,v^+_1,w^-_1) < 20 \cdot \partial_2(G_6). \end{aligned}
\end{equation*}
\notag
$$
Отметим, что последнее неравенство является строгим, так как из условия $\operatorname{deg}_{G_6}(u_1) \geqslant 2$ следует, что $\partial_2(G_6,u_1^-,v_1^+,w_1^+) \geqslant 1$. Случай 8 ($G$ содержит треугольник $uvw$, в котором все вершины имеют степень 3, при этом хотя бы две из соседних вершин $u_1$, $v_1$ и $w_1$ – считаем, что это $u_1$ и $v_1$ – имеют степень 2). Заметим, что некоторые из вершин $u_1$, $v_1$, $w_1$ могут быть смежны, на ход рассуждений это не влияет. Обозначим через $G_1$ результат удаления ребра $uv$ и изолированной вершины. Из (3.11) следует неравенство $i(G) \geqslant (3/2) \cdot i(G_1)$. Осталось доказать неравенство (4.1). Из рассуждений случая 4 следует, что для этого достаточно доказать (4.2). Покажем, что
$$
\begin{equation*}
4 \cdot \partial_2^*(G,G_1,u^-,v^+) \leqslant 2 \cdot \partial_2(G_1,u^-,v^+)+\partial_2(G_1,u^+,v^+).
\end{equation*}
\notag
$$
Заметим, что каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^-)$ содержит вершину $u_1$. Кроме того, каждое 2-ДМ $D_1 \in \mathfrak{D}_2(G_1,u^-)$ содержит как вершину $u_1$, так и вершину $w$. Тогда получаем
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^-,v^+) &=\partial_2(G,u^-,v^+,w^-,u^+_1) \stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^-,v^+,w^+,u^+_1) \\ &=\partial_2(G_1,u^-,v^+,w^+,u^+_1) \stackrel{{(3.5)}}{\leqslant} \partial_2(G_1,u^-,v^+). \end{aligned}
\end{equation*}
\notag
$$
Кроме того,
$$
\begin{equation*}
\begin{aligned} \, 2 \cdot \partial_2^*(G,G_1,u^-,v^+) &=2 \cdot \partial_2(G,u^-,v^+,w^-,u^+_1) \\ &\!\stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^+,v^+,w^-,u^+_1)+\partial_2(G,u^+,v^+,w^+,u^+_1) \\ &\!\!\!\!\!\!\stackrel{{(3.3), (3.5)}}{\leqslant} \partial_2(G,u^+,v^+)=\partial_2(G_1,u^+,v^+). \end{aligned}
\end{equation*}
\notag
$$
Аналогично доказывается неравенство
$$
\begin{equation*}
4 \cdot \partial_2^*(G,G_1,u^+,v^-) \leqslant 2 \cdot \partial_2(G_1,u^+,v^-)+\partial_2(G_1,u^+,v^+),
\end{equation*}
\notag
$$
откуда получаем $\partial_2(G) \leqslant (3/2) \cdot \partial_2(G_1)$. Отметим, что использование более простого преобразования из случая 8 для случая 7 не приводит к желаемому результату. С другой стороны, использование преобразования из случая 7 для случая 8 не позволяет применить лемму 9. Случай 9 ($G$ содержит вершину $u$ степени не менее 3, которая смежна с вершиной $v$ степени 3 и не имеет с ней общих соседей). Обозначим через $u_1,\dots,u_s$ соседей вершины $u$ и через $v_1$, $v_2$ соседей вершины $v$. Случай 9a: $\operatorname{deg}(u) \geqslant 4$. Обозначим через $G_1$ граф, полученный из $G$ удалением ребра $uv$ и изолированной вершины. Не умаляя общности, считаем, что $\operatorname{deg}(u) \geqslant \max\{\operatorname{deg}(v_1),\operatorname{deg}(v_2)\}$. Покажем, что Из рассуждений случая 6b следует, что достаточно доказать соотношение
$$
\begin{equation}
5 \cdot i(G_1,u^+,v^+) \leqslant i(G_1,u^-,v^+)+i(G_1,u^+,v^-)+ i(G_1,u^-,v^-).
\end{equation}
\tag{4.18}
$$
Мы предполагаем, что все соседи $u$ имеют степень не более 3 (иное было уже разобрано в случае 4). Если $\operatorname{deg}(u) \geqslant 5$, то
$$
\begin{equation*}
i(G_1,u^-,v^-) \stackrel{{(3.8)}}{\geqslant} i(G_1,u^-,v^+) \stackrel{{(3.12)}}{\geqslant} 2 \cdot i(G_1,u^+,v^+),
\end{equation*}
\notag
$$
откуда следует (4.18). Пусть теперь $\operatorname{deg}(u)=4$, тогда $\max\{\operatorname{deg}(v_1),\operatorname{deg}(v_2)\} \leqslant 4$ по предположению. В этом случае из (3.12) следует, что
$$
\begin{equation*}
i(G_1,u^-,v^+) \geqslant \frac{7}{4} \cdot i(G_1,u^+,v^+), \qquad i(G_1,u^+,v^-) \geqslant \frac{5}{4} \cdot i(G_1,u^+,v^+).
\end{equation*}
\notag
$$
Кроме того,
$$
\begin{equation*}
i(G_1,u^-,v^-) \geqslant \frac 54 \cdot i(G_1,u^-,v^+) > 2 \cdot i(G_1,u^+,v^+),
\end{equation*}
\notag
$$
откуда снова следует (4.18). Из условия $\operatorname{deg}_G(u) \geqslant 4$ следует, что граф $G_1$ не 2-регулярен, таким образом, $i(G_1) > \partial_2(G_1)$ по предположению и достаточно доказать неравенство
$$
\begin{equation*}
\partial_2(G) \leqslant \frac 53 \cdot \partial_2(G_1).
\end{equation*}
\notag
$$
Из рассуждений случая 4 следует, что достаточно доказать неравенство
$$
\begin{equation}
\begin{aligned} \, \notag &\partial_2^*(G,G_1,u^-,v^+)+\partial_2^*(G,G_1,u^+,v^-) \\ &\qquad \leqslant \frac 23 \cdot \bigl(\partial_2(G_1,u^-,v^+)+\partial_2(G_1,u^+,v^-)+ \partial_2(G_1,u^+,v^+)\bigr). \end{aligned}
\end{equation}
\tag{4.19}
$$
Разобьем доказательство на два шага. Шаг 1. Докажем неравенство
$$
\begin{equation}
3 \cdot \partial_2^*(G,G_1,u^-,v^+) \leqslant 2 \cdot \partial_2(G_1,u^-,v^+)+\frac 12 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.20}
$$
Покажем, что $\partial_2^*(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^-,v^+)$. Положим $U_i=N(u) \setminus \{u_i,v\}$, $1 \leqslant i \leqslant s$, тогда получаем
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^-,v^+) &= \sum_{i=1}^k \partial_2(G,u^-,v^+,U^-_i,u^+_i) \stackrel{{(3.9)}}{\leqslant} \sum_{i=1}^k \partial_2(G,u^-,v^+,U^+_i,u^-_i) \\ &=\sum_{i=1}^k \partial_2(G_1,u^-,v^+,U^+_i,u^-_i) \stackrel{{(3.1)}}{<} \partial_2(G_1,u^-,v^+). \end{aligned}
\end{equation*}
\notag
$$
Теперь покажем, что $ 2 \cdot \partial_2^*(G,G_1,u^-,v^+) \leqslant \partial_2(G_1,u^+,v^+)$:
$$
\begin{equation*}
\begin{aligned} \, 2 \cdot \partial_2^*(G,G_1,u^-,v^+) &=2 \cdot \sum_{i=1}^k \partial_2(G,u^-,v^+,U^-_i,u^+_i) \\ &\!\stackrel{{(3.7)}}{\leqslant} 2 \cdot \sum_{i=1}^k \partial_2(G,u^+,v^+,U^-_i,u^+_i) \\ &\!\stackrel{{(3.9)}}{\leqslant} \sum_{i=1}^k \partial_2(G_1,u^+,v^+,U^-_i,u^+_i) +\sum_{i=1}^k \partial_2(G_1,u^+,v^+,U^+_i,u^-_i) \\ &\!\stackrel{{(3.1)}}{<} \partial_2(G_1,u^+,v^+). \end{aligned}
\end{equation*}
\notag
$$
Шаг 2. Докажем неравенство
$$
\begin{equation}
3 \cdot \partial_2^*(G,G_1,u^+,v^-) \leqslant 2 \cdot \partial_2(G_1,u^+,v^-)+\frac 43 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.21}
$$
Покажем, что $2 \cdot \partial^*_2(G,G_1,u^+,v^-) \leqslant (4/3) \cdot \partial_2(G_1,u^+,v^+)$:
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^+,v^-) &=\partial_2(G,u^+,v^-,v^+_1,v^-_2)+ \partial_2(G,u^+,v^-,v^-_1,v^+_2) \\ &\!\stackrel{{(3.7)}}{\leqslant} \frac 23 \cdot \bigl( \partial_2(G,u^+,v^+,v^-_1,v^+_2)+\partial_2(G,u^+,v^+,v^+_1,v^-_2) \\ &\qquad+ \partial_2(G,u^+,v^+,v^+_1,v^+_2)\bigr) \\ &\!\stackrel{{(3.1)}}{\leqslant} \frac 23 \cdot \partial_2(G,u^+,v^+)=\frac 23 \cdot \partial_2(G_1,u^+,v^+). \end{aligned}
\end{equation*}
\notag
$$
Теперь покажем, что $\partial^*_2(G,G_1,u^+,v^-) \leqslant 2 \cdot \partial_2(G_1,u^+,v^-)$:
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^+,v^-) &=\partial_2(G,u^+,v^-,v^+_1,v^-_2)+ \partial_2(G,u^+,v^-,v^-_1,v^+_2) \\ &\!\stackrel{{(3.7)}}{\leqslant} 2 \cdot \partial_2(G,u^+,v^-,v^+_1,v^+_2)=2 \cdot \partial_2(G_1,u^+,v^-,v^+_1,v^+_2) \\ &\!\stackrel{{(3.5)}}{\leqslant} 2 \cdot \partial_2(G_1,u^+,v^-). \end{aligned}
\end{equation*}
\notag
$$
Из неравенств (4.20) и (4.21) следует (4.19), что и требовалось. Случай 9b: $\operatorname{deg}(u)=3$. Будем считать, что компонента связности $H$, содержащая $u$ и $v$, не является 3-регулярной и не содержит висячих вершин (иное уже было разобрано в случаях 1 и 3). Кроме того, будем считать, что каждая вершина степени более 3 в $H$ смежна только с вершинами степени 2 (иное уже было разобрано в случаях 4 и 9a). При этом, поскольку $H$ не 3-регулярна, в ней содержится хотя бы одна вершина $w$ степени 2. Рассмотрим кратчайший путь из вершины $v$ в вершину $w$. Ясно, что на этом пути найдется хотя бы одна вершина степени 3, смежная с вершиной степени 3 и вершиной степени 2. Переименуем вершины $H$ таким образом, чтобы вершины $u$ и $v$ были смежными вершинами степени 3 и хотя бы одна из вершин, соседних с $v$ (считаем, что это $v_2$), имела степень 2. Удалим из $G$ ребро $uv$ и изолированную вершину, обозначим через $G_1$ полученный граф. Из условий $\max\{\operatorname{deg}(u_1),\operatorname{deg}(u_2),\operatorname{deg}(v_1)\} \leqslant 3$ и $\operatorname{deg}(v_2)=2$ следует, что
$$
\begin{equation*}
i(G_1,u^+,v^-) \stackrel{{(3.12)}}{\geqslant} \frac 74 \cdot i(G_1,u^+,v^+), \qquad i(G_1,u^-,v^+) \stackrel{{(3.12)}}{\geqslant} \frac32\cdot i(G_1,u^+,v^+).
\end{equation*}
\notag
$$
Из (3.12) следует, что $i(G_1,u^-,v^-) > i(G_1,u^+,v^-)$, тогда получаем
$$
\begin{equation}
5 \cdot i(G_1,u^+,v^+) < i(G_1,u^-,v^+)+i(G_1,u^+,v^-)+i(G_1,u^-,v^-).
\end{equation}
\tag{4.22}
$$
Аналогично случаю 9a из (4.22) следует $i(G) > (5/3) \cdot i(G_1)$. Остается доказать, что $\partial_2(G) \leqslant (5/3) \cdot \partial_2(G_1)$. Как и в случае 9a, для этого достаточно доказать (4.19). Разобьем доказательство на два шага. Шаг 1. Докажем, что
$$
\begin{equation}
3 \cdot \partial_2^*(G,G_1,u^-,v^+) \leqslant 2 \cdot \partial_2(G_1,u^-,v^+)+\frac 43 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.23}
$$
Заметим, что каждое 2-ДМ $D \in \mathfrak{D}_2(G,u^-,v^+)$ содержит хотя бы одну из вершин $u_1$ и $u_2$. С другой стороны, каждое 2-ДМ $D' \in \mathfrak{D}_2(G_1,u^-,v^+)$ содержит обе эти вершины. Тогда выполняются соотношения
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^-,v^+) &=\partial_2(G,u^-,u^+_1,u^-_2,v^+)+ \partial_2(G,u^-,u^-_1,u^+_2,v^+) \\ &\!\stackrel{{(3.7)}}{\leqslant} 2 \cdot \partial_2(G,u^-,u^+_1,u^+_2,v^+) =2 \cdot \partial_2(G_1,u^-,u^+_1,u^+_2,v^+) \\ &\!\stackrel{{(3.5)}}{\leqslant} 2 \cdot \partial_2(G_1,u^-,v^+), \\ 2 \cdot \partial_2^*(G,G_1,u^-,v^+) &=2 \cdot (\partial_2(G,u^-,u^+_1,u^-_2,v^+)+\partial_2(G,u^-,u^-_1,u^+_2,v^+)) \\ &\!\stackrel{{(3.7)}}{\leqslant} \frac 43 \cdot \bigl(\partial_2(G_1,u^+,u^+_1,u^-_2,v^+)+ \partial_2(G_1,u^+,u^-_1,u^+_2,v^+) \\ &\qquad+\partial_2(G_1,u^+,u^+_1,u^+_2,v^+)\bigr) \\ &\!\stackrel{{(3.1)}}{\leqslant} \frac 43 \cdot \partial_2(G_1,u^+,v^+), \end{aligned}
\end{equation*}
\notag
$$
из которых и следует (4.23). Шаг 2. Докажем, что
$$
\begin{equation}
3 \cdot \partial_2^*(G,G_1,u^+,v^-) \leqslant 2 \cdot \partial_2(G_1,u^+,v^-)+ \frac 12 \cdot \partial_2(G_1,u^+,v^+).
\end{equation}
\tag{4.24}
$$
Поскольку $\operatorname{deg}(v_2)=2$, то каждое 2-ДМ $D \in \mathfrak{D}_2(G,v^-)$ содержит $v_2$. Таким образом, выполнены соотношения
$$
\begin{equation*}
\begin{aligned} \, \partial_2^*(G,G_1,u^+,v^-) &=\partial_2(G,u^+,v^-,v^-_{1},v^+_{2} ) \stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^+,v^-,v^+_{1},v^+_{2}) \\ &=\partial_2(G_1,u^+,v^-,v^+_{1},v^+_{2}) \stackrel{{(3.5)}}{\leqslant} \partial_2(G_1,u^+,v^-), \\ 2 \cdot \partial_2^*(G,G_1,u^+,v^-) &=2 \cdot \partial_2(G,u^+,v^-,v^-_{1},v^+_{2}) \\ &\!\stackrel{{(3.7)}}{\leqslant} \partial_2(G,u^+,v^+,v^-_{1},v^+_{2})+ \partial_2(G,u^+,v^+,v^+_{1},v^+_{2}) \\ &\!\!\!\!\!\! \stackrel{{(3.3), (3.5)}}{\leqslant} \partial_2(G,u^+,v^+)=\partial_2(G_1,u^+,v^+), \end{aligned}
\end{equation*}
\notag
$$
из которых вытекает (4.24). Из неравенств (4.23) и (4.24) следует (4.19), что и требовалось. Случай 10 (все вершины степени более 2 графа $G$ попарно несмежны). Обозначим через $G^*$ граф, полученный из $G$ удалением всех его изолированных вершин (рис. 2). Рассмотрим произвольное множество $D \in \mathfrak{D}_2(G^*)$. Ясно, что хотя бы один из концов каждого ребра $G^*$ входит в $D$, иначе в $G^*$ нашлась бы вершина степени 2, не входящая в $D$, хотя бы один из соседей которой также не входит в $D$, что невозможно. Но тогда $V(G^*) \setminus D \in \mathfrak{I}(G^*)$ и отображение $F(D)=V(G^*) \setminus D$ является инъекцией из $\mathfrak{D}_2(G^*)$ в $\mathfrak{I}(G^*)$, таким образом, получаем $\partial_2(G)=\partial_2(G^*) \leqslant i(G^*) < i(G)$, что и требовалось. Теорема 2 доказана. § 5. ЗаключениеМетоды, используемые в работе при рассмотрении случая $k=2$, оказываются малоэффективными в случае $k \geqslant 3$ по двум причинам. Во-первых, $k$-регулярные графы при $k \geqslant 3$, в отличие от 2-регулярных графов, имеют нетривиальную структуру. Кроме того, любой нерегулярный граф со средней степенью вершин не более 2 обязательно содержит хотя бы одну висячую или изолированную вершину; для графов со средней степенью вершин не более $k$ при $k \geqslant 3$ аналогичное утверждение неверно. Таким образом, лемма 9 об изолированных вершинах, имеющая большое значение для случая $k=2$, не может быть использована при $k \geqslant 3$. Во-вторых, преобразования, используемые в случае $k=2$, заключались в основном в удалении одинакового количества вершин и ребер из графа. В случае $k \geqslant 3$ такого рода преобразования должны быть устроены значительно сложнее. Так, при $k=3$ на каждые две удаленные вершины должно приходиться не менее, чем три удаленных ребра (в противном случае средняя степень вершин графа увеличится), а удалять одну вершину и два ребра, по всей видимости, нецелесообразно. По мнению автора, наиболее перспективным направлением дальнейших исследований является рассмотрение некоторых важных классов графов, имеющих естественное ограничение на среднюю степень вершин (таких, как субкубические, внешнепланарные и планарные графы). Структура таких графов значительно проще, чем структура произвольных графов с такой же средней степенью вершин. Например, каждый максимальный внешнепланарный граф является гамильтоновым, а каждое внутреннее ребро такого графа разбивает его на два максимальных внешнепланарных подграфа меньшего размера. Вероятно, использование структурных свойств подобного рода позволит разработать новые подходы к решению рассматриваемой задачи. 
Цитирование в формате AMSBIB
\RBibitem{Tal23} |
|
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|