
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}

\def\udcs{519.174.5} %Здесь автор определяет УДК своей работы
\def\mscs{05C70} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{conjecture}{Гипотеза}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 22, стр. XXX--YYY (2025) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
        {\rm\small DOI~10.17377/semi.2025.01.xx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}

\thispagestyle{empty}

\title[Новое доказательство теоремы Нэш-Вильямса]{Новое доказательство теоремы Нэш-Вильямса и его применения}
\author{{А.Н. ГЛЕБОВ}}
\address{Aleksey Nikolaevich Glebov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}
\email{angle@math.nsc.ru}

\thanks{\sc Glebov, A.N.,
A new proof of Nash-Williams' Theorem and its applications}
\thanks{\copyright \ 2024 Глебов A.Н}
\thanks{\rm Работа выполнена в рамках государственного задания ИМ СО РАН
(проект №  FWNF-2022-0017).}
\thanks{\it Поступила ?? декабря 2024 г., опубликована X Y 2025 г.}


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } The famous Nash-Williams' Theorem
states that the edge set of a multigraph $G=(V,E)$ can be decomposed
into $k$ forests iff for every subset $X\subseteq V$ the induced subgraph
$G[X]$ contains at most $k(|X|-1)$ edges. In 2017, Glebov conjectured
that if a graph $G$ satisfies the conditions of Nash-Williams' Theorem
and has minimum degree $\delta(G)\ge k+1$, then its edge set can be
decomposed into $k$ forests such that none of these forests has an
isolated vertex. Here we prove this conjecture. Moreover, we present
a new proof of Nash-Williams' Theorem which allows us to prove a more
general result on edge decomposition of a  multigraph into $k$ forests
such that the size of connected components in these forests is greater
than a given constant.
\medskip

\noindent{\bf Keywords:} graph, multigraph, tree, forest,
decomposition, arboricity, Nash-Williams' Theorem, cover index.
 \end{quote}
}

\section{Введение}

В настоящей работе через $G=(V,E)$ обозначается конечный
неориентированный мультиграф с множеством вершин $V$
и множеством рёбер $E$, Через $v(G)=|V|$ и $e(G)=|E|$
обозначается число вершин и число рёбер мультиграфа $G$
соответственно. Будем говорить, что ребро $e\in E$ {\em
инцидентно} вершине $v\in V$ (или что $e$ {\em покрывает}
$v$), если вершина $v$ является концом ребра $e$. {\em
Степенью} $d(v)$ вершины $v\in V$ в $G$ называется число
инцидентных $v$ рёбер. Через $\delta(G)$ и $\Delta(G)$
обозначается минимальная и максимальная степень вершины
мультиграфа $G$ соответственно. Для каждой пары вершин
$u,v\in V$ через $\mu(uv)$ обозначается {\em кратность
мультиребра} $uv$ в $G$, то есть количество рёбер в $E$
с концами $u$ и $v$. Через $\mu(G)$ обозначается
максимальная кратность мультиребра в мультиграфе $G$.
Ясно, что $G$ является простым графом тогда и только
тогда, когда $\mu(G) \le 1$.

{\em Лесом} называется простой граф без циклов. Для
каждого подмножества вершин $X\subseteq V$ мультиграфа
$G$ через $G[X]$ обозначается подграф в $G$, {\em
порождённый} множеством вершин $X$. Для каждого
подмножества рёбер $F\subseteq E$ через $G<F>=(V,F)$
обозначается подграф в $G$ с множеством вершин $V$ и
множеством рёбер $F$.

{\em Раскраской рёбер} мультиграфа $G=(V,E)$ в $k$
цветов (или {\em $k$-раскраской рёбер} $G$) называется
произвольное отображение $c:E \rightarrow K$,
где $K=\{ 1,2,\ldots,k\}$ называется
{\em множеством цветов}. Для каждого ребра $e\in E$
число $c(e)$ называется {\em цветом} ребра $e$. Для
каждого цвета $i\in K$ через $E_i$ обозначается
соответствующий ему {\em цветовой класс}, то есть
множество $E_i=c^{-1}(i)$ всех рёбер цвета $i$ в $G$.
Раскраску рёбер мультиграфа $G$ назовём {\em древесной},
если для каждого цветового класса $E_i$ соответствующий
подграф $G<E_i>$ является лесом.

Раскраску рёбер $G$ назовём {\em покрывающей}, если
каждая вершина мультиграфа $G$ покрыта рёбрами всех
цветов, то есть каждый цветовой класс $E_i$ является
{\em рёберным покрытием} $G$. Далее мы рассмотрим
более общее понятие $t$-покрывающей раскраски рёбер.
Пусть $t$ --- натуральное число. Раскраску рёбер
мультиграфа $G$ назовём {\em $t$-покрывающей}, если
для любого цвета $i\in K$ каждая компонента связности
соответствующего подграфа $G<E_i>$ содержит не менее
$t$ вершин. Из данных определений следует, что
покрывающая раскраска рёбер мультиграфа является
частным случаем $t$-покрывающей раскраски при $t=2$.

Иногда при изучении раскрасок рёбер графов и мультиграфов
бывает полезно рассматривать ситуации, когда одновременно
выполняются два важных свойства, каждое из которых
заслуживает быть предметом самостоятельного исследования.
Так в работе \cite{Gleb} изучались раскраски рёбер
мультиграфов, которые одновременно являются древесными и
покрывающими. Иными словами, в \cite{Gleb} исследовались
такие древесные раскраски рёбер мультиграфов, что множество
рёбер каждого цвета порождает лес без изолированных вершин.

Хорошо известен следующий критерий существования
древесной раскраски рёбер мультиграфа в $k$ цветов:

\begin{theorem} (Нэш-Вильямс)
\cite{N-W1961,N-W1964} Для мультиграфа $G=(V,E)$ существует
древесная $k$-раскраска рёбер, если и только если для любого
подмножества вершин $X\subseteq V$ число рёбер в порождённом
подграфе $G[X]$ не превосходит $k(|X|-1)$.
\end{theorem}

Наименьшее число $k$, для которого существует древесная
$k$-раскраска рёбер мультиграфа $G$ называется его {\em
древесностью} и обозначется через $\gamma(G)$. Из теоремы
Нэш-Вильямса следует явная формула для вычисления древесности
мультиграфа: $\gamma(G)=\lceil Arb(G)\rceil$, где число
$$Arb(G)=\max \left \{ \frac {e(G[X])}{|X|-1} \, | \, X
\subseteq V, \, |X|>1 \right \}$$
называется {\em дробной древесностью} мультиграфа $G$.

Что касается покрывающей раскраски рёбер мультиграфа, Гуптой
\cite{G1967,G1978} были получены следующие достаточные условия
её существования.

\begin{theorem}
\cite{G1967,G1978} Пусть $G$ --- мультиграф с минимальной
степенью $\delta(G)$ и максимальной кратностью мультиребра
$\mu(G)$. Тогда существует покрывающая раскраска рёбер $G$
в $\delta(G)-\mu(G)$ цветов. При этом если $G$ --- двудольный
граф, то существует покрывающая раскраска рёбер $G$
в $\delta(G)$ цветов.
\end{theorem}

В \cite{Gleb} было доказано, что при определённых условиях
одновременное выполненеие требований из теорем 1 и 2 влечёт
существование такой $k$-раскраски рёбер мультиграфа, которая
одновременно является древесной и покрывающей.

\begin{theorem} \cite{Gleb}
Пусть $k\ge 2$ --- целое число, и $G=(V,E)$ --- мультиграф с
древесностью $\gamma(G)\le k$, удовлетворяющий одному из условий:

(1) $G$ --- двудольный и $\delta(G)\ge k$;

(2) $k=2$ и $\delta(G)\ge 3$.

Тогда существует древесная покрывающая $k$-раскраска рёбер $G$.
\end{theorem}

Также в \cite{Gleb} была сформулирована следующая

\begin{conjecture} \cite{Gleb}
Для любого графа $G$ с древесностью $\gamma(G)\le k$ и минимальной
степенью $\delta(G)\ge k+1$ существует древесная покрывающая
$k$-раскраска рёбер.
\end{conjecture}

В \cite{Gleb} было отмечено, что оценка на минимальную степень графа
в гипотезе 1 является неулучшаемой, что следует из существования
$k$-регулярного графа $G$ с $\chi'(G)=k+1$. В настояшей работе
подтверждается справедливость гипотезы 1 и доказывается следующий
более общий факт:

\begin{theorem}
Пусть для мультиграфа $G$ существует древесная $k$-раскраска
его рёбер (т.е. $\gamma(G)\le k$) и существует $t$-покрывающая
$k$-раскраска рёбер $G$. Тогда существует древесная $t$-покрывающая
$k$-раскраска рёбер $G$.
\end{theorem}

Заметим, что из теорем 2 и 4 (при $t=2$) следует справедливость
гипотезы 1 а также тот факт, что для двудольного графа $G$ с
древесностью $\gamma(G)\le k$ и минимальной степенью $\delta(G)
\ge k$ существует древесная покрывающая $k$-раскраска рёбер.

Предложенное ниже доказательство теоремы 4 основано на
преобразовании произвольной $k$-раскраски рёбер мультиграфа
в его древесную $k$-раскраску путём последовательной перекраски
рёбер. Назовём перекраску ребра $e=uv$ из цвета $i$ в цвет $j$
{\em цикловой перекраской}, если в подграфе $G<E_i>$ ребро $e$
принадлежит какому-либо циклу. Заметим, что после цикловой
перекраски ребра $e$ все множества вершин компонент связности
подграфа $G<E_i>$ не меняются, а множества вершин компонент
связности подграфа $G<E_j>$ либо не меняются (если в этом
подграфе вершины $u$ и $v$ принадлежат одной компоненте),
либо два таких подмножества  (содержащие вершины $u$ и $v$
соответственно) объединяются в одно подмножество. Таким
образом, при любой последовательности цикловых перекрасок
множества вершин всех компонент связности во всех подграфах
$G<E_m>$ ($m=1,\ldots,k$) могут только увеличиваться. Отсюда
следует, что если начальная $k$-раскраска рёбер мультиграфа $G$
является $t$-покрывающей, то и полученная в конце $k$-раскраска
рёбер $G$ также является $t$-покрывающей.

Наш основной результат о цикловой перекраске рёбер состоит в
следующем:

\begin{theorem}
Пусть для мультиграфа $G$ существует древесная $k$-раскраска
его рёбер (т.е. $\gamma(G)\le k$). Тогда из любой начальной
$k$-раскраски рёбер $G$ последовательностью цикловых перекрасок
можно получить древесную $k$-раскраску рёбер $G$.
\end{theorem}

Заметим, что из теоремы 5 следует как теорема 1 (Нэш-Вильямса),
так и теорема 4. Последний факт следует из того, что если в
качестве начальной $k$-раскраски рёбер $G$ в теореме 5 выбрать
$t$-покрывающую раскраску, то согласно сделанному выше замечанию,
эта раскраска будет преобразована в древесную $t$-покрывающую
$k$-раскраску рёбер $G$.

Таким образом, для доказательства теоремы 4 и гипотезы 1
достаточно доказать теорему 5. Этому доказательству посвящена
оставшаяся часть статьи.


\section{Доказательство теоремы о цикловой перекраске рёбер}

Пусть мультиграф $G=(V,E)$ является контрпримером к теореме 5
с минимальным числом рёбер. Очевидно, что $|E|>1$.
Рассмотрим произвольную начальную $k$-раскраску $c_0:E
\rightarrow K=\{ 1,2,\ldots,k\}$ рёбер $G$. Выберем
произвольное ребро $e_0=ab\in E$. Без ограничения общности
будем считать, что $c_0(e_0)=1$. Рассмотрим в $G$ подграф
$G'=G-e_0$ с множеством вершин $V$ и множеством рёбер
$E'=E\setminus \{e_0\}$. Обозначим через $c'_0$ ограничение
$k$-раскраски $c_0$ на множество рёбер $E'$. Из минимальности
контрпримера $G$ следует, что раскраска $c'_0$ может быть
последовательностью цикловых перекрасок преобразована в
древесную $k$-раскраску $c'$ рёбер подграфа $G'$. Очевидно,
что все указанные перекраски являются также цикловыми
перекрасками рёбер мультиграфа $G$, где в качестве начальной
раскраски выбрана $c_0$. Таким образом, раскраска $c_0$ с помошью
указанной последовательности цикловых перекрасок преобразуется
в такую $k$-раскраску $c_1$ рёбер $G$, что все подграфы
$G<E_i>$ при $i=2,\ldots,k$ являются лесами, а подграф $G<E_1>$
либо является лесом, либо содержит единственный цикл $C_0$,
включающий в себя ребро $e_0$. Если $G<E_1>$ --- лес, то
раскраска $c_1$ является искомой древесной $k$-раскраской
рёбер $G$.

Допустим, что подграф $G<E_1>$ содержит единственный цикл
$C_0=(V_0,E_0)$, где $e_0 \in E_0$. Тогда при любой цикловой
перекраске произвольного ребра $e\in E_0$ в любой цвет $j \in
\{ 2,\ldots,k\}$ подграф $G<E_1>$ становится лесом, а подграф
$G<E_j>$ либо остаётся лесом, либо в нём появляется единственный
цикл $C$, включающий в себя ребро $e$. В первом случае цикловую
перекраску ребра $e$ назовём {\em успешной}. Ясно, что после
успешной перекраски образуется искомая древесная $k$-раскраска
рёбер $G$.

Допустим, что перекраска ребра $e$ в цвет $j$ не является
успешной. Тогда подграф $G<E_j>$ содержит единственный цикл
$C$, а все другие подграфы $G<E_m>$ при $m\neq j$ являются
лесами. В таком случае последовательность цикловых перекрасок
можно продолжить, перекрашивая любое ребро $e'\in C$ в любой
цвет $m\neq j$. Если эту последовательность перекрасок можно
продолжить таким образом, что в какой-то момент она оканчивается
успешной перекраской, то получаем искомую древесную $k$-раскраску
рёбер $G$.

Допустим, что никакая последовательность цикловых перекрасок
рёбер $G$, начинающаяся с раскраски $c_1$, не оканчивается
успешной перекраской. Тогда для любой $k$-раскраски рёбер $G$,
полученной из раскраски $c_1$ путём последовательных цикловых
перекрасок рёбер, в точности один подграф $G<E_i>$ содержит
единственный цикл $C$, а все другие подграфы $G<E_m>$ при
$m\neq i$ являются лесами. Будем говорить, что вершина $v\in V$
является {\em $C$-достижимой}, если из раскраски $c_1$
последовательностью цикловых перекрасок можно получить
такую $k$-раскраску рёбер $G$, что вершина $v$ принадлежит
единственному циклу $C$ в соответствующем подграфе $G<E_i>$.
Обозначим множество всех $C$-достижимых вершин мультиграфа
$G$ через $Z$, а порождённый ими подграф $G[Z]$ --- через
$H=(Z,E_H)$.

Для каждого $j=1,\ldots,k$ положим $E'_j = E_j \cap E_H$,
где $E_j$ --- множество всех рёбер цвета $j$ в раскраске
$c_1$. Рассмотрим в $H$ подграфы $H_j = H<E'_j> = (Z,E'_j)$,
где $j=1,\ldots,k$. Будем считать, что при цикловой перекраске
ребра $e \in E'_i$ из цвета $i$ в любой другой цвет $m$
ребро $e$ переносится из множества $E'_i$ в множество $E'_m$
(а также из множества $E_i$ в $E_m$). Тогда после любой
последовательности цикловых перекрасок для каждого
$j=1,\ldots,k$ выполняется равенство $E'_j = E_j \cap E_H$.
Таким образом, множества рёбер всех подграфов $H_j$ в любой
момент образуют разбиение множества рёбер мультиграфа $H$,
то есть выполняется равенство $E_H = E'_1 \cup E'_2 \cup
\ldots \cup E'_k$.

Из существования древесной $k$-раскраски рёбер $G$ и из
теоремы 1, применённой к множеству $X=Z$, следует неравенство
$$k(|Z|-1) \ge |E_H|=|E'_1|+|E'_2|+\ldots +|E'_k|. \eqno (1)$$
Из определения множеств $Z$ и $E'_1$ следует, что $V_0
\subseteq Z$, $E_0 \subseteq E'_1$. Следовательно, цикл
$C_0$ содержится в подграфе $H_1$. Аналогично, после любой
последовательности цикловых перекрасок, начинающейся
с раскраски $c_1$, все вершины полученного цикла $C$
принадлежат $Z$, а все его рёбра --- одному из подмножеств
$E'_i$, где $i\in \{ 1,2,\ldots,k\}$. Тогда цикл $C$
содержится в подграфе $H_i$.

Докажем, что для некоторого $j\in \{ 1,2,\ldots,k\}$ подграф
$H_j$ является несвязным. Предположим, что для каждого
$j=1,2,\ldots,k$ подграф $H_j$ связен. Тогда $|E'_j| \ge |Z|-1$
и $|E'_1| \ge |Z|$, так как подграф $H_1$ содержит цикл $C_0$.
Отсюда следует, что $|E'_1|+|E'_2|+\ldots +|E'_k| > k(|Z|-1)$,
что противоречит (1). Следовательно, существует $j\in \{ 1,2,
\ldots,k\}$, для которого подграф $H_j$ не является связным.
Обозначим через $Z_1$ множество вершин какой-либо компоненты
связности в $H_j$. Положим $Z_2=Z\setminus Z_1$. Тогда $Z_2
\neq \emptyset$ и в $H_j$ (а значит, и в $E_j$) нет рёбер,
соединяющих вершины из $Z_1$ с вершинами из $Z_2$.

{\em Случай 1.} Цикл $C_0$ содержит хотя бы одну вершину из
$Z_1$ и хотя бы одну вершину из $Z_2$. В этом случае в $C_0$
есть ребро $e=xy$ такое, что $x\in Z_1$, $y\in Z_2$.
Следовательно, $j\neq 1$. Докажем, что цикловая перекраска
ребра $e$ из цвета 1 в цвет $j$ является успешной. Допустим,
что после указанной перекраски в подграфе $G<E_j>$ образуется
цикл $C$. Тогда $e\in C$. Из определения множества $Z$ следует,
что все вершины цикла $C$ принадлежат $Z$. Поэтому цикл $C$
содержится в подграфе $H_j$. Тогда до перекраски ребра $e$
в цвет $j$ в подграфе $H_j$ имеется $(x,y)$-цепь $P=C-e$,
где $x\in Z_1$, $y\in Z_2$. Это противоречит определению
множеств $Z_1$ и $Z_2$. Следовательно, перекраска ребра $e$
в цвет $j$ является успешной.

{\em Случай 2.} Все вершины цикла $C_0$ содержатся в одном из
множеств $Z_1$ или $Z_2$. Предположим, что $V_0 \subseteq
Z_1$. Случай $V_0 \subseteq Z_2$ рассматривается аналогично.
Из определения множества $Z$ следует, что существует такая
последовательность цикловых перекрасок рёбер, начинающаяся
с раскраски $c_1$, что для полученного цикла $C$ в подграфе
$H_i$ какая-то его вершина $z$ принадлежит множеству $Z_2$.
Рассмотрим минимальную такую последовательность цикловых
перекрасок. Тогда при последней из этих перекрасок какое-то
ребро $e'=x'y'$, принадлежащее циклу $C'$ в некотором подграфе
$H_m$, перекрашивается в цвет $i$. При этом все вершины цикла
$C'$ принадлежат множеству $Z_1$. Так как после перекраски
ребра $e'=x'y'$ в цвет $i$ это ребро принадлежит циклу $C$
в подграфе $H_i$, то цикл $C$ содержит вершины $x',y' \in
Z_1$, а также вершину $z\in Z_2$. Отсюда следует, что в цикле
$C$ имеется такое ребро $e=xy$, что $x\in Z_1$, $y\in Z_2$.
Получили ситуацию, аналогичную случаю 1, где вместо цикла
$C_0$ рассматривается цикл $C$. Аналогично случаю 1,
доказывается, что цикловая перекраска ребра $e$ в цвет $j$
является успешной. \, Теорема 5 доказана.

\bigskip
\begin{thebibliography}{1}

\bibitem{Gleb} A.N.Glebov,
{\it An enhancement of Nash-Williams' Theorem on edge arboricity of
graphs}, Siberian Electronic Mathematical Reports,
{\bf 11} (2017), 1324--1329.

\bibitem{G1967} R.P. Gupta,
{\it Studies in the theory of graphs}, Ph.D. Thesis, Tata Institute
of Fundamental Research, Bombay (1967).

\bibitem{G1978} R.P. Gupta,
{\it On the chromatic index and the cover index of a multigraph},
In: Y. Alavi, D.R. Lick (eds) Theory and Applications of Graphs.
Lecture Notes in Mathematics, {\bf 642}. Springer, Berlin,
Heidelberg (1978), 204--215.

\bibitem{N-W1961} C.St.J.A. Nash-Williams,
{\it Edge-disjoint spanning trees of finite graphs}, J. London Math.
Soc., {\bf 36} (1961), 445--450.

\bibitem{N-W1964} C.St.J.A. Nash-Williams,
{\it Decomposition of finite graphs into forests}, J. London Math.
Soc., {\bf 39} (1964), 12.

\end{thebibliography}

\end{document}
