\documentclass[11pt,reqno]{amsart}
\usepackage{titlesec}
%\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
\usepackage{tikz}
\usetikzlibrary {arrows.meta}
\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

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

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


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

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

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



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


\thispagestyle{empty}

\title[\sc $\text{УЗЛОВЫЕ}\,\, \text{КОМПОНЕНТЫ}\,\, \text{4-ИЗЯЩНЫХ}\,\, \text{ДЕРЕВЬЕВ}$]{\large $\text{УЗЛОВЫЕ}\,\, \text{КОМПОНЕНТЫ}\,\, \text{4-ИЗЯЩНЫХ}\,\, \text{ДЕРЕВЬЕВ}$}
%\author[В.А.~БАРАНСКИЙ, И.А.~НАСЫРОВ, Т.А.~СЕНЬЧОНОК]{{\bf \large \textsc{В.А.~Баранский, И.А.~Насыров, Т.А.~Сеньчонок}}\protect\orcidicon{0000-0001-8827-2630}\\ \\
\author[В.А.~БАРАНСКИЙ, И.А.~НАСЫРОВ, Т.А.~СЕНЬЧОНОК]{{\bf \large \textsc{В.А.~Баранский, И.А.~Насыров, Т.А.~Сеньчонок}}\\ \\
\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Baransky Vitaly Anatolievich  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Ural Federal University,
\newline\hphantom{iii} Lenina av., 51,
\newline\hphantom{iii} 620000, Ekaterinburg, Russia}%
\email{\textcolor{blue}{vitaly.baransky@urfu.ru}}%

\address{Nasyrov Ilia Aleksandrovich  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Ural Federal University,
\newline\hphantom{iii} Lenina av., 51,
\newline\hphantom{iii} 620000, Ekaterinburg, Russia}%
\email{\textcolor{blue}{ilia.nasyrov@urfu.ru}}%

\address{Senchonok Tatiana Aleksandrovna  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Ural Federal University,
\newline\hphantom{iii} Lenina av., 51,
\newline\hphantom{iii} 620000, Ekaterinburg, Russia}%
\email{\textcolor{blue}{tatiana.senchonok@urfu.ru}}%

\thanks{\sc Baransky, V.A., Nasyrov I.A., Senchonok T.A.,
Nodal components of 4-graceful trees}
\thanks{\copyright \ 2025 Баранский В.А., Насыров И.А., Сеньчонок Т.А.}
%\thanks{\rm Работа поддержана РФФИ (грант 03-01-11111)}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} Let $f$ be a coloring of the vertices of a connected graph $G$ into colors from the set of colors $\{1, 2, \dots, k\}$. A coloring $f$ on the set of edges of a graph $G$ induces a function $f'(e) = |f(u) - f(v)|$, where $e = uv$ is an arbitrary edge of the graph $G$. The number $f'(e)$ will be called the \textit{weight} of the edge $e$ \textit{induced by the coloring} $f$.
          
A coloring $f$ is called a \textit{graceful $k$-coloring} of a graph $G$ if $f'$ is an edge coloring of this graph. We will call a graph an \textit{$k$-graceful graph} or, simply, a \textit{graceful graph} if it has a graceful $k$-coloring.

In general, 4-graceful trees are quite complex. Note that 3-graceful connected graphs have a very simple structure. They are among simple chains of length no more than 3.

It is easy to establish that any 4-graceful graph does not contain vertices of degree greater than 3. Therefore, we consider trees $T$ whose vertex degrees do not exceed 3. Vertices of degree 3 in a tree $T$ we will call by \textit{nodes}. We will say that the \textit{nodal distance} between two nodes $u$ and $v$ of a tree $T$ is equal to $s$ if there is a simple chain from $u$ to $v$ such that the number of internal vertices in it is equal to $s$ and all these internal vertices have degree 2 in the tree $T$. (Of course, the nodal distance is defined not for any pair of nodes.) In this case, we will call a simple chain from $u$ to $v$ an \textit{$s$-branch}.

Let us fix some positive integer $s$ and generate a subgraph $T_s$ of the tree $T$ from all nodes and all $s$-branches. The connected components of $T_s$ will be called \textit{nodal $s$-components} (or simply \textit{nodal components}) of the tree $T$. 

The main goal of our work is as follows. 
\begin{enumerate}
    \item For all positive integers $s$, find 4-graceful colorings of $s$-branches with given pairs of colors for the initial and final nodes (see Tables~\ref{tab1}, \ref{tab2} and \ref{tab3}).
    \item To consider the properties of 4-graceful colorings of nodal $s$-components for $s\geq 4$ and $s\neq 5$ (see Theorems~\ref{t1} and \ref{t2}).
    \item To show how can be found forbidden configurations for 4-graceful trees with using nodal $s$-components (see Theorem~\ref{t3}).
\end{enumerate}

\medskip

\noindent{\bf Keywords:} graph, tree, graceful coloring of a graph, 4-graceful trees.
 \end{quote}
}

\bigskip

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

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

Пусть $G$ --- связный граф и $f$ --- его $k$-раскраска вершин, т.\,е. раскраска в \textit{краски} (или \textit{цвета}) из множества красок $\{1, 2, \dots, k\}$ (далее всюду под раскрасками графа мы будем понимать его правильные раскраски). Раскраска $f$ индуцирует следующую функцию $f'$ на множестве рёбер этого графа: 
$f'(e) = | f(u) - f(v) |,$
где $e = uv$ --- произвольное ребро графа $G$, т.\,е. $f'(e)$ равно модулю разности цветов концевых вершин ребра $e$. Число $f'(e)$ будем называть \textit{весом} ребра $e$, \textit{индуцированным раскраской} $f$.

Раскраска $f$ называется \textit{изящной $k$-раскраской} (graceful k-coloring) графа $G$, если $f'$ является рёберной раскраской этого графа (иными словами, является раскраской рёберного графа для $G$). Граф будем называть \textit{$k$-изящным} (k-graceful graph) или, просто, \textit{изящным} (graceful graph), если он обладает изящной $k$-раскраской. Для изящного графа $G$ наименьшее число $k$ такое, что граф $G$ является $k$-изящным, будем называть \textit{изящным хроматическим числом} этого графа.

Понятие изящной $k$-раскраски графа ввел Г.~Шартран в 2015 году. В динамическом обзоре \cite{4} можно найти множество результатов, родственных результатам о изящных раскрасках графов. В последние годы были найдены изящные хроматические числа для многих классов графов, большое внимание было уделено изучению изящных деревьев (см., например, \cite{5}--\cite{8}). 

Отметим, что связные 3-изящные графы устроены очень просто, они исчерпываются простыми цепями длины не более 3. Задача же характеризации 4-изящных деревьев оказался весьма непростой. Нетрудно заметить, что любой 4-изящный граф не содержит вершин степени большей 3. Поэтому для 4-изящных деревьев естественно искать характеризацию в классе деревьев, у которых максимальная степень вершин $\Delta = 3$. Вершины степени 3 мы будем называть \textit{узлами} (nodes) дерева.

Будем говорить, что для двух узлов $u$ и $v$ дерева $T$ \textit{узловое расстояние} между ними равно числу $s$, если существует простая цепь от $u$ до $v$, число внутренних вершин в которой равно $s\geq 0$ и все эти внутренние вершины имеют степень 2 в дереве $T$ (конечно, число вершин в такой цепи равно $s + 2$, а длина цепи равна $s + 1$). Простую цепь от $u$ до $v$ будем называть в таком случае \textit{$s$-ветвью}. Изображая $s$-ветви (и подграфы деревьев), мы будем выделять узлы малыми кругами (на Рис.~\ref{ris1} изображена 4-ветвь).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (2,0) circle (4pt);
\draw (0,0) -- (2,0);
\fill (4,0) circle (4pt);
\draw (2,0) -- (4,0);
\draw (4,0) -- (6,0);
\fill (6,0) circle (4pt);
\draw (6,0) -- (8,0);
\fill (8,0) circle (4pt);
\draw (8,0) -- (10,0);
\fill (10,0) circle (4pt);
\draw (10,0) circle (9pt);
\end{tikzpicture}
\caption{4-ветвь}
\label{ris1}
\end{center}
\end{figure}

Подграфы дерева $T$ с выделенными узлами из $T$ будем называть \textit{конфигурациями}.

В работе \cite{2} нами были найдены следующие достаточные условия 4-изящности деревьев.
\begin{enumerate}
    \item Пусть $T$ --- дерево, степени вершин которого не превосходят 3, и которое не содержит простых цепей, состоящих из трех узлов. Если такое дерево $T$ не имеет пар узлов, узловые расстояния между которыми равны 1 или 2 (т.\,е. нет конфигураций вида: \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.5,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) circle (9pt);
\draw (1.5,0) -- (3,0);
\fill (3,0) circle (4pt);
\draw (3,0) circle (9pt);
\end{tikzpicture}, \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.5,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) -- (3,0);
\fill (3,0) circle (4pt);
\draw (3,0) circle (9pt);
\end{tikzpicture}, \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.35,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) -- (3,0);
\fill (3,0) circle (4pt);
\draw (3.,0) -- (4.5,0);
\fill (4.5,0) circle (4pt);
\draw (4.5,0) circle (9pt);
\end{tikzpicture}), то оно является 4-изящным. 
    \item Пусть $T$ --- дерево, степени вершин которого не превосходят 3 и которое не содержит пар смежных узлов. Если такое дерево $T$ не имеет пар узлов, узловые расстояния между которыми равны 1 (т.е. нет конфигураций вида: \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.5,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) circle (9pt);
\end{tikzpicture}, \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.5,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) -- (3,0);
\fill (3,0) circle (4pt);
\draw (3,0) circle (9pt);
\end{tikzpicture}), то оно является 4-изящным.  
\end{enumerate}

В данной работе мы продолжим изучение изящных раскрасок в классе деревьев, в которых максимальная степень вершин $\Delta = 3$ (т.\,е. будем предполагать, что в дереве имеется хотя бы один узел). Наша цель ---  рассмотреть строение таких деревьев и выделить способы построения среди них 4-изящных и не 4-изящных деревьев. 

Зафиксируем некоторое натуральное число $s$ и породим всеми узлами и всеми $s$-ветвями подграф $T_s$ дерева $T$. Компоненты связности этого леса $T_s$ будем называть \textit{узловыми $s$-компонентами} (или просто \textit{узловыми компонентами}) дерева $T$ (см. Рис.~\ref{ris2}), т.\,е. под узловыми компонентами дерева $T$ мы будем понимать его узловые $s$-компоненты для натуральных чисел $s$.


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\fill (0,-1) circle (4pt);
\draw (0,0) -- (0,-1);
\fill (0,-2) circle (4pt);
\draw (0,-2) circle (9pt);
\draw (0,-1) -- (0,-2);
%right
\fill (1.5,-3) circle (4pt);
\draw (0,-2) -- (1.5,-3);
\fill (3,-4) circle (4pt);
\draw (1.5,-3) -- (3,-4);
\fill (4.5,-5) circle (4pt);
\draw (4.5,-5) circle (9pt);
\draw (3,-4) -- (4.5,-5);
\fill (6,-6) circle (4pt);
\draw (6,-6) -- (4.5,-5);
\fill (4.5,-6) circle (4pt);
\draw (4.5,-5) -- (4.5,-6);
\fill (4.5,-7) circle (4pt);
\draw (4.5,-7) -- (4.5,-6);
\fill (4.5,-8) circle (4pt);
\draw (4.5,-7) -- (4.5,-8);
\fill (4.5,-9) circle (4pt);
\draw (4.5,-9) -- (4.5,-8);
\fill (4.5,-10) circle (4pt);
\draw (4.5,-10) circle (9pt);
\draw (4.5,-9) -- (4.5,-10);
%right
\fill (5,-11) circle (4pt);
\draw (5,-11) -- (4.5,-10);
\fill (5.5,-12) circle (4pt);
\draw (5,-11) -- (5.5,-12);
\fill (6,-13) circle (4pt);
\draw (6,-13) -- (5.5,-12);
\fill (6.5,-14) circle (4pt);
\draw (6,-13) -- (6.5,-14);
\fill (7,-15) circle (4pt);
\draw (7,-15) circle (9pt);
\draw (7,-15) -- (6.5,-14);
\fill (7.5,-16) circle (4pt);
\draw (7,-15) -- (7.5,-16);
\fill (6.5,-16) circle (4pt);
\draw (7,-15) -- (6.5,-16);
%left
\fill (4,-11) circle (4pt);
\draw (4,-11) -- (4.5,-10);
\fill (3.5,-12) circle (4pt);
\draw (4,-11) -- (3.5,-12);
\fill (3,-13) circle (4pt);
\draw (3,-13) -- (3.5,-12);
\fill (2.5,-14) circle (4pt);
\draw (3,-13) -- (2.5,-14);
\fill (2,-15) circle (4pt);
\draw (2,-15) circle (9pt);
\draw (2,-15) -- (2.5,-14);
\fill (1.5,-16) circle (4pt);
\draw (2,-15) -- (1.5,-16);
\fill (1,-17) circle (4pt);
\draw (1,-17) -- (1.5,-16);
\fill (2.5,-16) circle (4pt);
\draw (2,-15) -- (2.5,-16);
\fill (3,-17) circle (4pt);
\draw (3,-17) circle (9pt);
\draw (3,-17) -- (2.5,-16);
\fill (3.5,-18) circle (4pt);
\draw (3,-17) -- (3.5,-18);
\fill (2.5,-18) circle (4pt);
\draw (3,-17) -- (2.5,-18);
%left
\fill (-1.5,-3) circle (4pt);
\draw (0,-2) -- (-1.5,-3);
\fill (-3,-4) circle (4pt);
\draw (-1.5,-3) -- (-3,-4);
\fill (-4.5,-5) circle (4pt);
\draw (-4.5,-5) circle (9pt);
\draw (-3,-4) -- (-4.5,-5);
%left
\fill (-6,-6) circle (4pt);
\draw (-4.5,-5) -- (-6,-6);
\fill (-7.5,-7) circle (4pt);
\draw (-7.5,-7) -- (-6,-6);
\fill (-9,-8) circle (4pt);
\draw (-9,-8) circle (9pt);
\draw (-7.5,-7) -- (-9,-8);

\fill (-10.5,-9) circle (4pt);
\draw (-10.5,-9) -- (-9,-8);
\fill (-12,-10) circle (4pt);
\draw (-10.5,-9) -- (-12,-10);
\fill (-13.5,-11) circle (4pt);
\draw (-13.5,-11) -- (-12,-10);

\fill (-9,-9) circle (4pt);
\draw (-9,-9) -- (-9,-8);
\fill (-9,-10) circle (4pt);
\draw (-9,-10) circle (9pt);
\draw (-9,-9) -- (-9,-10);
\fill (-8.5,-11) circle (4pt);
\draw (-8.5,-11) -- (-9,-10);
\fill (-9.5,-11) circle (4pt);
\draw (-9.5,-11) -- (-9,-10);
\fill (-10,-12) circle (4pt);
\draw (-9.5,-11) -- (-10,-12);
%right
\fill (-4.5,-6) circle (4pt);
\draw (-4.5,-6) circle (9pt);
\draw (-4.5,-5) -- (-4.5,-6);
\fill (-5,-7) circle (4pt);
\draw (-5,-7) -- (-4.5,-6);
\fill (-5.5,-8) circle (4pt);
\draw (-5,-7) -- (-5.5,-8);
\fill (-6,-9) circle (4pt);
\draw (-6,-9) -- (-5.5,-8);
\fill (-6.5,-10) circle (4pt);
\draw (-6.5,-10) circle (9pt);
\draw (-6,-9) -- (-6.5,-10);
\fill (-7,-11) circle (4pt);
\draw (-7,-11) -- (-6.5,-10);
\fill (-7.5,-12) circle (4pt);
\draw (-7,-11) -- (-7.5,-12);
\fill (-8,-13) circle (4pt);
\draw (-8,-13) -- (-7.5,-12);
\fill (-8.5,-14) circle (4pt);
\draw (-8.5,-14) circle (9pt);
\draw (-8,-13) -- (-8.5,-14);
\fill (-9,-15) circle (4pt);
\draw (-9,-15) -- (-8.5,-14);
\fill (-8,-15) circle (4pt);
\draw (-8,-15) -- (-8.5,-14);

\fill (-6,-11) circle (4pt);
\draw (-6,-11) -- (-6.5,-10);
\fill (-5.5,-12) circle (4pt);
\draw (-6,-11) -- (-5.5,-12);
\fill (-5,-13) circle (4pt);
\draw (-5,-13) -- (-5.5,-12);
\fill (-4.5,-14) circle (4pt);
\draw (-4.5,-14) circle (9pt);
\draw (-5,-13) -- (-4.5,-14);
\fill (-4,-15) circle (4pt);
\draw (-4,-15) -- (-4.5,-14);
\fill (-5,-15) circle (4pt);
\draw (-5,-15) -- (-4.5,-14);

\fill (-4,-7) circle (4pt);
\draw (-4,-7) -- (-4.5,-6);
\fill (-3.5,-8) circle (4pt);
\draw (-4,-7) -- (-3.5,-8);
\fill (-3,-9) circle (4pt);
\draw (-3,-9) -- (-3.5,-8);
\fill (-2.5,-10) circle (4pt);
\draw (-2.5,-10) circle (9pt);
\draw (-3,-9) -- (-2.5,-10);
\fill (-2,-11) circle (4pt);
\draw (-2,-11) -- (-2.5,-10);
\fill (-1.5,-12) circle (4pt);
\draw (-2,-11) -- (-1.5,-12);
\fill (-1,-13) circle (4pt);
\draw (-1,-13) -- (-1.5,-12);

\fill (-3,-11) circle (4pt);
\draw (-3,-11) -- (-2.5,-10);
\fill (-3.5,-12) circle (4pt);
\draw (-3,-11) -- (-3.5,-12);

\draw[line width=.5pt, color=red] (0,-1.5) -- (-9,-7.5)  arc[start angle=90, end angle=270, radius=0.5cm] -- (0,-2.5) -- (4.5,-5.5) arc[start angle=-90, end angle=90, radius=0.5cm] -- cycle;
\draw[line width=.5pt, color=cyan] (-4.5,-6.5) -- (-6,-10) -- (-4,-14) arc[start angle=360, end angle=180, radius=0.5cm] -- (-6.5,-10.5) -- (-8,-14) arc[start angle=360, end angle=180, radius=0.5cm] -- (-5,-6) arc[start angle=180, end angle=0, radius=0.5cm] -- (-2,-10) arc[start angle=360, end angle=180, radius=0.5cm] -- cycle;
\draw[line width=.5pt, color=blue] (1.5,-15) arc[start angle=180, end angle=0, radius=0.5cm] -- (3.5,-17) arc[start angle=360, end angle=180, radius=0.5cm] -- cycle; 
\draw[line width=.5pt, color=blue] (-9.7,-8) arc[start angle=180, end angle=0, radius=0.7cm] -- (-8.3,-10) arc[start angle=360, end angle=180, radius=0.7cm] -- cycle;
\draw[line width=.5pt, color=gray] (-5.2,-5) arc[start angle=180, end angle=0, radius=0.7cm] -- (-3.8,-6) arc[start angle=360, end angle=180, radius=0.7cm] -- cycle;
\draw[line width=.5pt, color=green] (3.8,-5) arc[start angle=180, end angle=0, radius=0.7cm] -- (5.2,-10) -- (7.7,-15) arc[start angle=360, end angle=180, radius=0.7cm] -- (4.5,-10.7) -- (2.7,-15) arc[start angle=360, end angle=180, radius=0.7cm] -- (3.8,-10) -- cycle;
\end{tikzpicture}
\caption{Дерево и его узловые компоненты}
\label{ris2}
\end{center}
\end{figure}

Очевидно, все узлы дерева $T$ и все ветви порождают подграф $T^*$, который является объединением узловых компонент и который мы будем называть \textit{ядром} дерева $T$. Очевидно, что любые две различные узловые компоненты либо не пересекаются, либо имеют единственный общий узел (поскольку в дереве любые две различные вершины соединены точно одной простой цепью). Подграф $T^*$ можно представлять себе, как дерево узловых компонент. 

Пусть $G$ --- узловая компонента дерева $T$. Под \textit{расширенной узловой компонентой} $G'$ (отвечающей $G$) мы будем понимать подграф, который получается добавлением к $G$ всех рёбер, инцидентных узлам компоненты $G$ и не лежащих в этой компоненте, а также добавлением всех вершин, инцидентных добавляемым рёбрам. Ясно, что добавляемые рёбра и добавляемые вершины будут висячими в расширенной узловой компоненте $G'$ (см. Рис.~\ref{ris3}). Эти висячие рёбра и висячие вершины мы будем называть \textit{граничными} для $G$.

\begin{figure}[h]
\begin{minipage}[h]{0.49\linewidth}
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (0.5,-1) circle (4pt);
\draw (0,0) -- (0.5,-1);
\fill (1,-2) circle (4pt);
\draw (0.5,-1) -- (1,-2);
\fill (1.5,-3) circle (4pt);
\draw (1,-2) -- (1.5,-3);
\fill (2,-4) circle (4pt);
\draw (2,-4) circle (9pt);
\draw (1.5,-3) -- (2,-4);

\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (-0.5,-1) circle (4pt);
\draw (0,0) -- (-0.5,-1);
\fill (-1,-2) circle (4pt);
\draw (-0.5,-1) -- (-1,-2);
\fill (-1.5,-3) circle (4pt);
\draw (-1,-2) -- (-1.5,-3);
\fill (-2,-4) circle (4pt);
\draw (-2,-4) circle (9pt);
\draw (-1.5,-3) -- (-2,-4);

\fill (-2.5,-5) circle (4pt);
\draw (-2,-4) -- (-2.5,-5);
\fill (-3,-6) circle (4pt);
\draw (-2.5,-5) -- (-3,-6);
\fill (-3.5,-7) circle (4pt);
\draw (-3,-6) -- (-3.5,-7);
\fill (-4,-8) circle (4pt);
\draw (-4,-8) circle (9pt);
\draw (-3.5,-7) -- (-4,-8);

\fill (-1.5,-5) circle (4pt);
\draw (-2,-4) -- (-1.5,-5);
\fill (-1,-6) circle (4pt);
\draw (-1.5,-5) -- (-1,-6);
\fill (-.5,-7) circle (4pt);
\draw (-1,-6) -- (-.5,-7);
\fill (0,-8) circle (4pt);
\draw (0,-8) circle (9pt);
\draw (-.5,-7) -- (0,-8);
\end{tikzpicture}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\begin{tikzpicture}[scale=0.4]
\fill (0,1) circle (4pt);
\draw (0,0) -- (0,1);
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (0.5,-1) circle (4pt);
\draw (0,0) -- (0.5,-1);
\fill (1,-2) circle (4pt);
\draw (0.5,-1) -- (1,-2);
\fill (1.5,-3) circle (4pt);
\draw (1,-2) -- (1.5,-3);
\fill (2,-4) circle (4pt);
\draw (2,-4) circle (9pt);
\draw (1.5,-3) -- (2,-4);
\fill (2.5,-5) circle (4pt);
\draw (2.5,-5) -- (2,-4);
\fill (1.5,-5) circle (4pt);
\draw (1.5,-5) -- (2,-4);

\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (-0.5,-1) circle (4pt);
\draw (0,0) -- (-0.5,-1);
\fill (-1,-2) circle (4pt);
\draw (-0.5,-1) -- (-1,-2);
\fill (-1.5,-3) circle (4pt);
\draw (-1,-2) -- (-1.5,-3);
\fill (-2,-4) circle (4pt);
\draw (-2,-4) circle (9pt);
\draw (-1.5,-3) -- (-2,-4);

\fill (-2.5,-5) circle (4pt);
\draw (-2,-4) -- (-2.5,-5);
\fill (-3,-6) circle (4pt);
\draw (-2.5,-5) -- (-3,-6);
\fill (-3.5,-7) circle (4pt);
\draw (-3,-6) -- (-3.5,-7);
\fill (-4,-8) circle (4pt);
\draw (-4,-8) circle (9pt);
\draw (-3.5,-7) -- (-4,-8);
\fill (-3.5,-9) circle (4pt);
\draw (-3.5,-9) -- (-4,-8);
\fill (-4.5,-9) circle (4pt);
\draw (-4.5,-9) -- (-4,-8);

\fill (-1.5,-5) circle (4pt);
\draw (-2,-4) -- (-1.5,-5);
\fill (-1,-6) circle (4pt);
\draw (-1.5,-5) -- (-1,-6);
\fill (-.5,-7) circle (4pt);
\draw (-1,-6) -- (-.5,-7);
\fill (0,-8) circle (4pt);
\draw (0,-8) circle (9pt);
\draw (-.5,-7) -- (0,-8);
\fill (-0.5,-9) circle (4pt);
\draw (-.5,-9) -- (0,-8);
\fill (0.5,-9) circle (4pt);
\draw (.5,-9) -- (0,-8);
\end{tikzpicture}
\end{minipage}
\caption{Узловая компонента и её расширенная узловая компонента}
\label{ris3}
\end{figure}

Две граничные вершины расширенной узловой компоненты назовем \textit{близнецами}, если инцидентные им граничные рёбра являются смежными. На Рис.~\ref{ris3} изображена расширенная 3-узловая компонента, у которой среди висячих граничных вершин имеется три пары близнецов и одна висячая вершина, которая не имеет близнеца.  

Для нахождения 4-изящных раскрасок дерева $T$ естественно поочередно находить 4-изящные раскраски расширенных узловых компонент. В связи с этим важно уметь выделять запрещенные \textit{конфигурации} (т.\,е. подграфы дерева $T$ с отмеченными узлами из $T$), для которых не существует 4-изящных раскрасок.

Цель данной работы состоит в следующем.

\begin{enumerate}
    \item Для всех натуральных чисел $s$ найти 4-изящные раскраски $s$-ветвей с заданными парами красок для начальных и финальных узлов (см. Таблицы~\ref{tab1}, \ref{tab2} и \ref{tab3}). Именно такие раскраски систематически используются при нахождении 4-изящных раскрасок деревьев.
    \item Рассмотреть свойства 4-изящных раскрасок расширенных узловых $s$-компонент при $s\geq 4$ и $s\neq 5$ (см. Теоремы~\ref{t1} и \ref{t2}).
    \item Показать, как с помощью расширенных узловых $s$-компонент можно находить запрещённые конфигурации для 4-изящных деревьев (см. Теорему~\ref{t3}). 
\end{enumerate}

Заметим, что следующая наша работа будет посвящена изучению 4-изящных раскрасок расширенных узловых $s$-компонент при малых значениях $s$ и выделению запрещённых конфигураций по таким компонентам.      

\section{4-изящные раскраски ветвей}

Последовательность натуральных чисел $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_s)$ будем называть 4-изящной, если для любого $i = 1, \dots, s$ выполняется
\begin{enumerate}
    \item $\lambda_i \in \{1, 2, 3, 4\}$;
    \item $\lambda_i\neq\lambda_{i+1}$ при $i < s$;
    \item $|\lambda_{i + 1} - \lambda_i|\neq |\lambda_{i - 1} - \lambda_i|$ при $1 < i < s$.
\end{enumerate}

Заметим, что из (2) и (3) следует, что в 4-изящной последовательности любая тройка последовательных компонент $\lambda_i, \lambda_{i+1}, \lambda_{i+2}$ состоит из попарно различных чисел.

Легко проверить, что произвольная тройка $(a, b, c)$ попарно различных чисел из множества $\{1, 2, 3, 4\}$ является 4-изящной тогда и только тогда, когда она отлична от следующих четырёх \textit{запрещённых троек}
$$(1, 2, 3), (3, 2, 1), (2, 3, 4), (4, 3, 2),$$
т.\,е. из 24 троек попарно различных чисел множества $\{1, 2, 3, 4\}$ изящными являются 20 троек, а 4 тройки не являются изящными.

Будем рассматривать полугруппу слов над алфавитом $\{1, 2, 3, 4\}$ и каждую последовательность $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_s)$ чисел 1, 2, 3 и 4 будем представлять также в виде слова 
$$\lambda = \lambda_1\lambda_2\dots\lambda_s$$
(не путать с числом, записанным в десятеричной записи!) в этой полугруппе слов. Для удобства числа 1, 2, 3, 4 будем называть также \textit{буквами}.

Буквы 2 и 3 будем называть \textit{ординарными} (ordinary letters), а буквы 1 и 4 --- \textit{козырными} (trump letters).

Через $\varphi$ обозначим подстановку на множестве $\{1, 2, 3, 4\}$ такую, что
$$\varphi(1) = 4, \varphi(4) = 1 \text{ и } \varphi(2) = 3, \varphi(3) = 2.$$
Ясно, что $\varphi(x) = 5 - x$, откуда следует, что $\varphi$ сохраняет модуль разности букв:
$$|\varphi(a) - \varphi(b)|= |a - b|$$
для любых двух различных букв $a$ и $b$.

Слово 
$$\varphi(\lambda) = \varphi(\lambda_1) \varphi(\lambda_2) \dots \varphi(\lambda_s),$$
будем называть \textit{двойственным} для слова $\lambda = \lambda_1\lambda_2\dots\lambda_s$. Ясно, что слово $\varphi(\lambda)$ является 4-изящным тогда и только тогда, когда 4-изящно слово $\lambda$.

Заметим также, что если $f$ --- 4-изящная раскраска связного графа $G$, то суперпозиция $\varphi\circ f$, состоящая в замене $f$-красок вершин в соответствии с подстановкой $\varphi$, снова будет 4-изящной раскраской. Раскраску $\varphi\circ f$ будем называть \textit{двойственной раскраской} к раскраске $f$.  

Зафиксируем теперь связный граф $G$ и его 4-изящную раскраску $f$.

Маршрут $v_1, v_2, \dots, v_s$ в графе $G$ будем называть \textit{безвозвратным}, если для любого $i = 2, \dots, s - 1$ выполняется $v_{i - 1}\neq v_{i + 1}$. 

Нетрудно видеть, что последовательность цветов 
$$f(v_1)f(v_2)\dots f(v_s),$$
отвечающая безвозвратному маршруту $v_1, v_2, \dots, v_s$ в 4-изящном графе $G$, является 4-изящной последовательностью.

Нетрудно также заметить, что все 4-изящные последовательности исчерпываются безвозвратными маршрутами в графе $K_4$ с дорожными знаками, указанном на Рис.~\ref{ris4}. Четыре дорожных знака запрещают прохождение по маршрутам, отвечающим четырём запрещённым тройкам. На Рис.~\ref{ris4} запреты указаны с помощью закругленных стрелок. На Рис.~\ref{ris4} кроме раскрасок вершин для удобства указаны также веса рёбер. Заметим, что раскраска вершин графа $K_4$, указанная на Рис.~\ref{ris4}, не является 4-изящной.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.5]
\fill (0,0) circle (4pt) node[above] {4};
\draw (0,0) -- (-2,-2);
\fill (2,-2) circle (4pt) node[right] {3};
\draw (0,0) -- (2,-2);
\fill (0,-4) circle (4pt) node[below] {1};
\draw (0,-4) -- (2,-2);
\fill (-2,-2) circle (4pt) node[left] {2};
\draw (0,-4) -- (-2,-2);
\draw (0,-4) -- (0,0);
\draw (2,-2) -- (-2,-2);
\draw[node font=\itshape] (0.9,-1.1) node[above right, scale=.8] {1};
\draw[node font=\itshape] (-.9,-1.1) node[above left, scale=.8] {2};
\draw[node font=\itshape] (.9,-2.9) node[below right, scale=.8] {2};
\draw[node font=\itshape] (-.9,-2.9) node[below left, scale=.8] {1};
\draw[node font=\itshape] (-.1,-2.8) node[right, scale=.8] {3};
\draw[node font=\itshape] (-.8,-2.1) node[above, scale=.8] {1};
\draw [{Stealth}-{Stealth},  rounded corners] (-.6,-2.25) -- (-1.6,-2.2) -- (-.8,-2.85);
\draw [{Stealth}-{Stealth},  rounded corners] (.6,-1.75) -- (1.6,-1.8) -- (.8,-1.25);
\end{tikzpicture}
\caption{$K_4$ с четырьмя дорожными знаками}
\label{ris4}
\end{center}
\end{figure}

Рассматривая Рис.~\ref{ris4}, легко понять, что красками 2 и 3 нельзя в 4-изящных раскрасках графов раскрашивать узлы, так как при раскраске узла нужно будет использовать все три оставшиеся краски для раскраски соседей узла и тогда возникнут два смежных ребра одного цвета 1, что противоречиво (см. также леммы~1 и 2 из \cite{2}).

Поскольку красками 2 и 3 в 4-изящных раскрасках графов нельзя раскрашивать узлы, такие краски и названы \textit{ординарными} (ordinary letters). Краски же 1 и 4 при 4-изящных раскрасках графов можно использовать для раскрашивания любых вершин. Поэтому такие краски и называются \textit{козырными} (trump letters).

Поскольку козырных красок всего две, в 4-изящных графах не существует простых цепей, состоящих из трех различных узлов (т.\,е. нет конфигураций вида \begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\draw (0,0) -- (1.5,0);
\fill (1.5,0) circle (4pt);
\draw (1.5,0) circle (9pt);
\draw (1.5,0) -- (3,0);
\fill (3,0) circle (4pt);
\draw (3,0) circle (9pt);
\end{tikzpicture}).

Далее в Таблицах~\ref{tab1}, \ref{tab2} и \ref{tab3} мы указываем 4-изящные слова в алфавите красок $\{1, 2, 3, 4\}$, начинающиеся и заканчивающиеся козырными буквами. С помощью таких 4-изящных слов можно 4-изящно раскрашивать $s$-ветви, где $s$ принимает натуральные значения. 

\begin{table}[h]
    \centering
    \begin{tabular}{|l|l|c|c|c|c|}
        \hline
        Тип слова & Слово & $s=1$ & $s=4$ & $s=7$ & $s=10, 13, \dots$\\ \hline
        $12-21^+$ & $(124)^k$ 312 431 421 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $12-31$ & $(124)^k$ 312 431 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $12-41$ & $(124)^k$ 312 431 241 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $12-14$ & $(124)^k$ 314 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-24$ & $(124)^k$ 124 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-34^+$ & $(124)^k$ 134 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-21^+$ & $(134)^k$ 231 421 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $13-31$ & $(134)^k$ 231 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-41$ & $(134)^k$ 231 241 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $13-14$ & $(134)^k$ 214 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-24$ & $(134)^k$ 124 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-34^+$ & $(134)k$ 134 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-21^+$ & $(142)k$ 312 431 421 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $14-31$ & $(142)^k$ 312 431 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $14-41$ & $(142)^k$ 312 431 241 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $14-14$ & $(142)^k$ 314 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-24$ & $(143)^k$ 124 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-34^+$ & $(142)^k$ 134 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
    \end{tabular}
    \caption{$s\equiv1(3)$}
    \label{tab1}
\end{table}

В первом столбце таблиц в строках указывается \textit{тип 4-изящного слова}, т.\,е. пара, состоящая из его начала $uv$ длины 2 (\textit{2-префикс}) и его конца $pq$ длины 2 (\textit{2-суффикс}), где $u$ и $q$ --- козырные буквы. Такую пару мы будем записывать в виде $uv-pq$. Если 4-изящное слово состоит из $s + 2$ букв, т.\,е. его можно использоваться для 4-изящной раскраски $s$-ветвей, то его тип иногда будем записывать подробней в виде $uv-_s\hspace{-.25em}-pq$. Через $[uv-_s\hspace{-.25em}-pq]$ будем обозначать множество всех 4-изящных слов указанного типа $uv-_s\hspace{-.25em}-pq$. 

\begin{table}[h]
    \centering
    \begin{tabular}{|l|l|c|c|c|c|}
        \hline
        Тип слова & Слово & $s=2$ & $s=5$ & $s=8$ & $s=11, 14, \dots$\\ \hline
         &  &  &  &  & -- для $s=11$,\\ 
        $12-21^+$ & 12 $(431)^k$ 243 124 134 21 & -- & -- & -- & для $s>11$\\
         &  &  &  &  & $k=1, 2, \dots$\\ \hline
        $12-31$ & 12 $(431)^k$ 243 124 31 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $12-41$ & $(124)^k$ 124 1 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-14$ & 124 $(314)^k$ 231 4 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $12-24$ & $(124)^k$ 312 4  & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-34^+$ & $(124)^k$ 312 413 4 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $13-21^+$ & 134 213 42 $(134)^k$ 21 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $13-31$ & $(134)^k$ 213 423 1 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $13-41$ & 134 $(124)^k$ 1 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-14$ & 132 4 $(314)^k$ & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-24$ & 132 4 $(124)^k$ & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-34^+$ & 132 4 $(134)^k$  & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-21^+$ & $(142)^k$ 142 1 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-31$ & $(143)^k$ 143 1 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-41$ & $(143)^k$ 124 1 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-14$ & 1 $(421)^k$ 324 314 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $14-24$ & $(142)^k$ 312 4  & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-34^+$ & 1 $(421)^k$ 324 134 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
    \end{tabular}
    \caption{$s\equiv2(3)$}
    \label{tab2}
\end{table}

Если для заданной пары, состоящей из 2-префикса и 2-суффикса, $s$-ветвь не имеет 4-изящной раскраски с таким 2-префиксом и с таким 2-суффиксом, т.\,е. $[uv-_s\hspace{-.25em}-pq]=\emptyset$, то в столбце, соответствующем $s$, строка,  соответствующая этой паре, содержит прочерк. Если же такое 4-изящное слово существует, то указывается значение параметра $k$ для получения такого слова из слова, указанного во втором столбце таблицы. Отметим, что длина такого слова (т.\,е. число букв в нём) равна $s + 2$. Для каждого $s$ в таблицах мы указываем только одно из таких слов. Для наших целей этого вполне достаточно. 

В этих трёх таблицах все 2-префиксы начинаются с буквы 1. В силу двойственности для слов имеются ещё три таблицы, состоящие из двойственных слов, начинающихся с буквы 4. Выписывать их мы не будем, но использовать будем.

Отметим, что под нулевой степенью слова, как обычно, понимается пустой символ в полугруппе слов.  Отметим также, что 2-суффиксы вида 21 и 34 указаны со знаком $^+$. Это служебный символ, который будет использоваться в следующей работе авторов.  

\begin{table}[h]
    \centering
    \begin{tabular}{|l|l|c|c|c|c|}
        \hline
        Тип слова & Слово & $s=3$ & $s=6$ & $s=9$ & $s=12, 15, \dots$\\ \hline
        $12-21^+$ & 124 $(134)^k$ 21 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-31$ & 124 $(124)^k$ 31 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-41$ & $(124)^k$ 312 41 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $12-14$ & 12 $(413)^k$ 243 124 314 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $12-24$ & 12 $(431)^k$ 243 124 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $12-34^+$ & 12 $(431)^k$ 243 124 134 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
        $13-21^+$ & 134 $(134)^k$ 21 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-31$ & 134 $(124)^k$ 31 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-41$ & $(134)^k$ 132 41 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-14$ & 132 43 $(124)^k$ 314 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $13-24$ & $(134)^k$ 213 24 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $13-34^+$ & 13 $(421)^k$ 324 134 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $14-21^+$ & $(142)^k$ 134 21 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-31$ & $(142)^k$ 142 31 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-41$ & $(142)^k$ 132 41 & -- & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-14$ & $(142)^k$ 142 14 & $k=0$ & $k=1$ & $k=2$ & $k=3, 4, \dots$\\ \hline
        $14-24$ & 142 $(134)^k$ 213 24 & -- & -- & $k=1$ & $k=2, 3, \dots$\\ \hline
        $14-34^+$ & $(142)^k$ 312 431 421 34 & -- & -- & -- & $k=1, 2, \dots$\\ \hline
    \end{tabular}
    \caption{$s\equiv3(3)$}
    \label{tab3}
\end{table}

Рассматривая граф $K_4$ с дорожными знаками, который приведен на Рис.~\ref{ris4} , несложно проверить, что все слова, указанные в таблицах для всевозможных значений параметра $s$, являются 4-изящными и имеют нужные 2-префиксы и 2-суффиксы.

Теперь нужно обосновать правильность расстановки прочерков в таблицах. Мы начнём с малых значений $s$, равных 1, 2 и 3 (а затем рассмотрим значения $s\geq 4$). Для таких значений $s$ нетрудно найти всевозможные 4-изящные раскраски $s$-ветвей (см. Рис.~\ref{ris5}) и, используя их, обосновать появление прочерков в столбцах таблиц, отвечающих значениям $s = 1, 2, 3$.

Для перечисления всевозможных 4-изящных раскрасок $s$-ветвей для малых значений $s$ мы будем использовать простой алгоритм. Выписывая 4-изящное слово, мы последовательно будем добавлять новую букву в конец слова таким образом, чтобы она была отлична от двух последних букв растущего слова и не возникало запрещенной тройки букв. Сначала проведем этот процесс для $s = 1, 2, 3$ (см. Рис.~\ref{ris5}).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\node at (1,1.5) {$s=1$};
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[below] at (1,-.5) {$\underline{1\;\,2\;\,4}$};
\node[below] at (1,-1.8) {$\underline{1\;\,3\;\,4}$};
\fill (1,0) circle (4pt);
\draw (0,0) -- (1,0);
\fill (2,0) circle (4pt);
\draw (2,0) circle (9pt);
\draw (1,0) -- (2,0);
\node at (5,0) {типы};
\node[below right] at (3,-.5) {$12-24$};
\node[below right] at (3,-1.8) {$13-34^+$};

\node at (10.5,1.5) {$s=2$};
\fill (9,0) circle (4pt);
\draw (9,0) circle (9pt);
\node[below] at (10.5,-.5) {$\underline{1\;\,2\;\,4\;\,1}$};
\node[below] at (10.5,-1.8) {$1\;\,3\;\,2\;\,4$};
\node[below] at (10.5,-3.1) {$\underline{1\;\,3\;\,4\;\,1}$};
\node[below] at (10.75,-4.4) {$1\;\,4\;\,2\;\,1^+$};
\node[below] at (10.5,-5.7) {$\underline{1\;\,4\;\,3\;\,1}$};
\fill (10,0) circle (4pt);
\draw (9,0) -- (10,0);
\fill (11,0) circle (4pt);
\draw (11,0) -- (10,0);
\fill (12,0) circle (4pt);
\draw (12,0) circle (9pt);
\draw (11,0) -- (12,0);
\node at (15,0) {типы};
\node[below right] at (13,-.5) {$12-41$};
\node[below right] at (13,-1.8) {$13-24$};
\node[below right] at (13,-3.1) {$13-41$};
\node[below right] at (13,-4.4) {$14-21^+$};
\node[below right] at (13,-5.7) {$14-31$};

\node at (21,1.5) {$s=3$};
\fill (19,0) circle (4pt);
\draw (19,0) circle (9pt);
\node[below] at (21,-.5) {$\underline{1\;\,2\;\,4\;\,3\;\,1}$};
\node[below] at (21,-1.8) {$1\;\,3\;\,2\;\,4\;\,1$};
\node[below] at (21.25,-3.1) {$\underline{1\;\,3\;\,4\;\,2\;\,1}^+$};
\node[below] at (21,-4.4) {$1\;\,4\;\,2\;\,1\;\,4$};
\node[below] at (21,-5.7) {$1\;\,4\;\,3\;\,1\;\,4$};
\node[below] at (21,-7) {$\underline{1\;\,4\;\,2\;\,3\;\,1}$};
\fill (20,0) circle (4pt);
\draw (19,0) -- (20,0);
\fill (21,0) circle (4pt);
\draw (21,0) -- (20,0);
\fill (22,0) circle (4pt);
\draw (21,0) -- (22,0);
\fill (23,0) circle (4pt);
\draw (23,0) circle (9pt);
\draw (23,0) -- (22,0);
\node at (26,0) {типы};
\node[below right] at (24,-.5) {$12-31$};
\node[below right] at (24,-1.8) {$13-41$};
\node[below right] at (24,-3.1) {$13-21^+$};
\node[below right] at (24,-4.4) {$14-14$};
\node[below right] at (24,-5.7) {$14-14$};
\node[below right] at (24,-7) {$14-31$};
\end{tikzpicture}
\caption{Раскраски $s$-ветвей для $s=1, 2, 3$}
\label{ris5}
\end{center}
\end{figure}

Для случая $s = 3$ имеющиеся типы раскрасок 3-ветвей можно изобразить с помощью графа 3-переходов (см. Рис.~\ref{ris6}). Можно считать, что это двудольный граф, одну из долей которого составляют 6 всевозможных видов выходов 12, 13, 14, 41, 42 и 43 из узлов, другую долю составляют 6 всевозможных видов входов 21, 31, 41, 14, 24 и 34 в узлы, а $\{23, 32, 34, 43, 41, 14, 12, 21, 23, 32\}$ --- множество рёбер, отвечающих типам при $s = 3$ (конечно, при построении графа 3-переходов мы используем все типы 4-изящных раскрасок 3-ветвей, двойственные к указанным в Рис.~\ref{ris5}). Например, ребро 23 графа 3-переходов соединяет выход 12 с входом 31, т.\,е. отвечает типу $12-31$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[left] at (0,0) {$1$};
\fill (0,-2) circle (4pt);
\node[left] at (0,-2) {$2$};
\draw (0,0) -- (0,-2);
\fill (3,-5) circle (4pt);
\node[left] at (3,-5) {$3$};
\draw (3,-5) -- (0,-2);
\fill (3,-7) circle (4pt);
\node[left] at (3,-7) {$1$};
\draw (3,-7) circle (9pt);
\draw (3,-5) -- (3,-7);
\fill (0,-7) circle (4pt);
\draw (0,-7) circle (9pt);
\node[left] at (0,-7) {$1$};
\fill (0,-5) circle (4pt);
\node[left] at (0,-5) {$+2$};
\draw (0,-7) -- (0,-5);
\draw (3,-2) -- (0,-5);

\fill (3,0) circle (4pt);
\draw (3,0) circle (9pt);
\node[left] at (3,0) {$1$};
\fill (3,-2) circle (4pt);
\node[left] at (3,-2) {$3$};
\draw (3,0) -- (3,-2);
\fill (6,-5) circle (4pt);
\node[left] at (6,-5) {$4$};
\draw (6,-5) -- (3,-2);
\fill (6,-7) circle (4pt);
\node[left] at (6,-7) {$1$};
\draw (6,-7) circle (9pt);
\draw (6,-5) -- (6,-7);
\draw (6,-2) -- (3,-5);

\fill (6,0) circle (4pt);
\draw (6,0) circle (9pt);
\node[left] at (6,0) {$1$};
\fill (6,-2) circle (4pt);
\node[left] at (6,-2) {$4$};
\draw (6,0) -- (6,-2);
\fill (9,-5) circle (4pt);
\node[left] at (9,-5) {$1$};
\draw (9,-5) -- (6,-2);
\fill (9,-7) circle (4pt);
\node[left] at (9,-7) {$4$};
\draw (9,-7) circle (9pt);
\draw (9,-5) -- (9,-7);
\draw (9,-2) -- (6,-5);

\fill (9,0) circle (4pt);
\draw (9,0) circle (9pt);
\node[left] at (9,0) {$4$};
\fill (9,-2) circle (4pt);
\node[left] at (9,-2) {$1$};
\draw (9,0) -- (9,-2);
\fill (12,-5) circle (4pt);
\node[left] at (12,-5) {$2$};
\draw (12,-5) -- (9,-2);
\fill (12,-7) circle (4pt);
\node[left] at (12,-7) {$4$};
\draw (12,-7) circle (9pt);
\draw (12,-5) -- (12,-7);
\draw (12,-2) -- (9,-5);

\fill (12,0) circle (4pt);
\draw (12,0) circle (9pt);
\node[left] at (12,0) {$4$};
\fill (12,-2) circle (4pt);
\node[left] at (12,-2) {$2$};
\draw (12,0) -- (12,-2);
\fill (15,-5) circle (4pt);
\node[left] at (15,-5) {$+3$};
\draw (15,-5) -- (12,-2);
\fill (15,-7) circle (4pt);
\node[left] at (15,-7) {$4$};
\draw (15,-7) circle (9pt);
\draw (15,-5) -- (15,-7);
\draw (15,-2) -- (12,-5);

\fill (15,0) circle (4pt);
\draw (15,0) circle (9pt);
\node[left] at (15,0) {$4$};
\fill (15,-2) circle (4pt);
\node[left] at (15,-2) {$3$};
\draw (15,0) -- (15,-2);
\end{tikzpicture}
\caption{Граф 3-переходов}
\label{ris6}
\end{center}
\end{figure}

Для каждого натурального числа $s$ по таблицам~\ref{tab1}, \ref{tab2} и \ref{tab3} можно аналогично построить граф $s$-переходов. В этих таблицах при $s\geq 10$ и $s\neq 11$ нет прочерков, поэтому справедлива

\begin{lemma}\label{l1}
    Для любого $s$ такого, что $s\geq 10$ и $s\neq 11$, граф $s$-переходов является полным двудольным графом вида $K_{6,6}$.
\end{lemma}

Рассматривая таблицы, нетрудно заметить также справедливость двух следующих лемм.

\begin{lemma}\label{l2}
    Для любого $s = 4, 7, 8, 11$ граф $s$-переходов содержит полный двудольный подграф вида $K_{3,3}$, одна доля которого состоит из выходов $12, 13, 14$ из узлов цвета $1$, а вторая доля состоит из входов $14, 24, 34$ в узлы цвета $4$. 
\end{lemma}

\begin{lemma}\label{l3}
    Для любого $s = 6, 9$ граф $s$-переходов содержит полный двудольный подграф вида $K_{3,3}$, одна доля которого состоит из выходов $12, 13, 14$ из узлов цвета $1$, а вторая доля состоит из входов $21, 31, 41$ в узлы цвета $1$.
\end{lemma}

Конечно, справедливы (двойственные леммы) аналоги леммы~\ref{l2} для выходов 41, 42, 43 во входы 21, 31, 41 при $s = 4, 7, 8, 11$ и леммы~\ref{l3} для выходов 41, 42, 43 во входы 14, 24, 34 при $s = 6, 9$ в графах $s$-переходов. 

Продолжим обоснование наличия прочерков в столбцах таблиц для значений $s\geq4$.

Нетрудно сгенерировать все 4-изящные раскраски для 4-ветвей, 2-префикс которых начинается с буквы 1: 
$$124124,\; 124314,\; 124134;$$
$$134124,\; 132431,\; 134214,\; 134134,\; 134231;$$
$$142134,\; 143124,\; 142314.$$
Поэтому мы можем теперь выписать всевозможные типы 4-изящных раскрасок для 4-ветвей, префикс которых начинается с буквы 1:
$$12-_4\hspace{-.25em}-14,\; 12-_4\hspace{-.25em}-24,\; 12-_4\hspace{-.25em}-34;$$
$$13-_4\hspace{-.25em}-31,\; 13-_4\hspace{-.25em}-14,\; 13-_4\hspace{-.25em}-24,\; 13-_4\hspace{-.25em}-34;$$
$$14-_4\hspace{-.25em}-14,\; 14-_4\hspace{-.25em}-24,\; 14-_4\hspace{-.25em}-34.$$
Мы получили 10 типов при $s = 4$, для которых 4-изящные раскраски указаны в таблице~\ref{tab1}, для остальных типов при $s = 4$ указаны прочерки.

Для $s = 5$ мы проведем вычисления, аналогичные случаю $s = 4$. При $s\geq 6$ такие вычисления становятся громоздкими, поэтому мы изберем другой подход. Отметим, что для исследования прочерков в таблицах нужно рассматривать только значения $s\leq 11$.

Сгенерируем теперь все 4-изящные раскраски 5-ветвей, 2-префикс которых начинается с буквы 1:
$$1241241,\; 1243124,\; 1241324,\; 1241341;$$
$$1324124,\; 1341241,\; 1324314,\; 1324134,\; 1342134,\; 1341324,\; 1342314,\; 1341341;$$
$$1421324,\; 1431241,\; 1423124,\; 1421421,\; 1421341,\; 1421431,\; 1431431.$$
Теперь мы можем выписать всевозможные типы 4-изящных раскрасок 5-ветвей, 2-префикс которых начинается с буквы 1:
$$12-_5\hspace{-.25em}-41,\; 12-_5\hspace{-.25em}-24;$$
$$13-_5\hspace{-.25em}-41,\; 13-_5\hspace{-.25em}-14,\; 13-_5\hspace{-.25em}-24,\; 13-_5\hspace{-.25em}-34;$$
$$14-_5\hspace{-.25em}-21,\; 14-_5\hspace{-.25em}-31,\; 14-_5\hspace{-.25em}-41,\; 14-_5\hspace{-.25em}-24.$$
Мы получили 10 типов при $s = 5$, для которых 4-изящные раскраски указаны в таблице~\ref{tab2}, для остальных типов при $s = 5$ указаны прочерки.

Далее мы будем обосновывать прочерки в $s$ столбцах таблиц, используя ранее обоснованные прочерки в столбцах для меньших значений $s$ (т.\,е. прочерки в таблицах обосновываются ``рекуррентно'').

\begin{lemma}\label{l4}
    Не существует $4$-изящных раскрасок $6$-ветвей следующих типов:
    $$12-_6\hspace{-.25em}-14,\; 12-_6\hspace{-.25em}-24,\; 12-_6\hspace{-.25em}-34;$$ 
    $$13-_6\hspace{-.25em}-14,\; 13-_6\hspace{-.25em}-34;\; 14-_6\hspace{-.25em}-24,\; 14-_6\hspace{-.25em}-34.$$
\end{lemma}
\begin{proof}
1) Пусть от противного существует $f\in [12-_6\hspace{-.25em}-14]$. Тогда $f = 12a_1a_2a_3a_414$, где $a_1, a_2, a_3, a_4\in \{1, 2, 3, 4\}$. Ясно, что $a_1 = 4$, так как 123 --- запрещённая тройка, т.\,е. $f = 124a_2a_3a_414$.

\underline{1 случай.} $a_2 = 1$. Тогда $41a_3a_414\in [41-_4\hspace{-.25em}-14]$, откуда, переходя к двойственному слову, получаем $[14-_4\hspace{-.25em}-41]\neq\emptyset$, что невозможно (см. таблицу~\ref{tab1}, столбец при $s = 4$, тип $14-41$).

\underline{2 случай.} $a_2 = 3$. Тогда $43a_3a_414\in [43-_4\hspace{-.25em}-14]$, откуда, переходя к двойственному слову, получаем $[12-_4\hspace{-.25em}-41]\neq\emptyset$, что невозможно (см. таблицу~\ref{tab1}, столбец при $s = 4$, тип $12-41$).

2) Пусть от противного существует $f\in [12-_6\hspace{-.25em}-24]$. Тогда $f$ имеет вид: $f = 12a_1a_2a_3a_424$, где $a_1, a_2, a_3, a_4\in \{1, 2, 3, 4\}$. Ясно, что $a_1 = 4$ и $f = 124a_2a_3a_424$.

\underline{1 случай.} $a_2 = 1$. Тогда $41a_3a_424\in [41-_4\hspace{-.25em}-24]$, поэтому $[14-_4\hspace{-.25em}-31]\neq\emptyset$, что невозможно (см. таблицу~\ref{tab1}).

\underline{2 случай.} $a_2 = 3$. Тогда $43a_3a_424\in [43-_4\hspace{-.25em}-24]$, поэтому $[12-_4\hspace{-.25em}-31]\neq\emptyset$, что невозможно (см. таблицу~\ref{tab1}).

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

3) Пусть от противного существует $f\in [12-_6\hspace{-.25em}-34]$. Тогда $f$ имеет вид: $f = 12a_1a_2a_3a_434$ $\Rightarrow$ $f = 124a_2a_3a_434$.

Если $a_2 = 1$, то $41a_3a_434\in [41-_4\hspace{-.25em}-34]$ $\Rightarrow$ $[14-_4\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

Если $a_2 = 3$, то $43a_3a_434\in [43-_4\hspace{-.25em}-34]$ $\Rightarrow$ $[12-_4\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

4) Пусть от противного существует $f\in [13-_6\hspace{-.25em}-14]$. Тогда $f$ имеет вид: $f = 13a_1a_2a_3a_414$.

Если $a_4 = 2$, то $$f = 13a_1a_2a_3214\Rightarrow 13a_1a_2a_321\in [13-_5\hspace{-.25em}-21]\Rightarrow [13-_5\hspace{-.25em}-21] \neq \emptyset,$$ противоречие (см. таблицу~\ref{tab2}). 

Если $a_4 = 3$, то $$f = 13a_1a_2a_3314\Rightarrow 13a_1a_2a_331\in [13-_5\hspace{-.25em}-31]\Rightarrow [13-_5\hspace{-.25em}-31] \neq \emptyset,$$ противоречие (см. таблицу~\ref{tab2}).

5) Пусть от противного существует $f\in [13-_6\hspace{-.25em}-34]$. Тогда $f$ имеет вид: $f = 13a_1a_2a_3a_434\Rightarrow f = 13a_1a_2a_3134$.

Если $a_3 = 2$, то $13a_1a_221\in [13-_4\hspace{-.25em}-21]\Rightarrow [13-_4\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

Если $a_3 = 4$, то $13a_1a_241\in [13-_4\hspace{-.25em}-41]\Rightarrow [13-_4\hspace{-.25em}-41]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

6) Пусть от противного существует $f\in [14-_6\hspace{-.25em}-24]$. Тогда $f$ имеет вид: $f = 14a_1a_2a_3a_424$.

Если $a_1 = 2$, то $42a_2a_3a_424\in [42-_5\hspace{-.25em}-24]\Rightarrow [13-_5\hspace{-.25em}-31]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

Если $a_1 = 3$, то $43a_2a_3a_424\in [43-_5\hspace{-.25em}-24]\Rightarrow [12-_5\hspace{-.25em}-31]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

7) Пусть от противного существует $f\in [14-_6\hspace{-.25em}-34]$. Тогда $f$ имеет вид: $f = 14a_1a_2a_3a_434$.

Если $a_1 = 2$, то $42a_2a_3a_434\in [42-_5\hspace{-.25em}-34]\Rightarrow [13-_5\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

Если $a_1 = 3$, то $43a_2a_3a_434\in [43-_5\hspace{-.25em}-34]\Rightarrow [12-_5\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).
\end{proof}

\begin{lemma} \label{l5}
    Не существует $4$-изящных раскрасок $7$-ветвей следующих типов:
$$12-_7\hspace{-.25em}-21,\; 12-_7\hspace{-.25em}-41;$$ $$14-_7\hspace{-.25em}-21,\; 14-_7\hspace{-.25em}-41.$$
\end{lemma}
\begin{proof}
1) Пусть от противного существует $f\in [12-_7\hspace{-.25em}-21]$. Тогда $f = 12a_1a_2a_3a_4a_521$, где $a_1, a_2, a_3, a_4, a_5\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4421$.

Если $a_2 = 1$, то $41a_3a_4421\in [41-_5\hspace{-.25em}-21]\Rightarrow [14-_5\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

Если $a_2 = 3$, то $43a_3a_4421\in [43-_5\hspace{-.25em}-21]\Rightarrow [12-_5\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).
 
2) Пусть от противного существует $f\in [12-_7\hspace{-.25em}-41]$. Тогда $f$ имеет вид: $f = 12a_1a_2a_3a_4a_541$, где $a_1, a_2, a_3, a_4, a_5\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_541$.

Если $a_2 = 1$, то $41a_3a_4a_541\in [41-_5\hspace{-.25em}-41]\Rightarrow [14-_5\hspace{-.25em}-14]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

Если $a_2 = 3$, то $43a_3a_4a_541\in [43-_5\hspace{-.25em}-41]\Rightarrow [12-_5\hspace{-.25em}-14]\neq\emptyset$, противоречие (см. таблицу~\ref{tab2}).

3) Пусть от противного существует $f\in [14-_7\hspace{-.25em}-21]$. Тогда $f$ имеет вид: $f = 14a_1a_2a_3a_4a_521$, где $a_1, a_2, a_3, a_4, a_5\in \{1, 2, 3, 4\}$, поэтому $f = 14a_1a_2a_3a_4421$.

Если $a_1 = 2$, то $42a_2a_3a_4421\in [42-_6\hspace{-.25em}-21]$. При $a_4 = 1$ имеем $$42a_2a_314\in [42-_4\hspace{-.25em}-14]\Rightarrow [13-_4\hspace{-.25em}-41]\neq\emptyset,$$ противоречие (см. таблицу~\ref{tab1}); а при $a_4 = 3$ имеем $$42a_2a_334\in [42-_4\hspace{-.25em}-34]\Rightarrow [13-_4\hspace{-.25em}-21]\neq\emptyset,$$ противоречие (см. таблицу~\ref{tab1}).

Если $a_1 = 3$, то $43a_2a_3a_4421\in [43-_6\hspace{-.25em}-21]$. При $a_4 = 1$ имеем $$43a_2a_314\in [43-_4\hspace{-.25em}-14]\Rightarrow [12-_4\hspace{-.25em}-41]\neq\emptyset,$$ противоречие (см. таблицу~\ref{tab1}); а при $a_4 = 3$ имеем $$43a_2a_334\in [43-_4\hspace{-.25em}-34]\Rightarrow [12-_4\hspace{-.25em}-21]\neq\emptyset,$$ противоречие (см. таблицу~\ref{tab1}).

4) Пусть от противного существует $f\in [14-_7\hspace{-.25em}-41]$. Тогда $f$ имеет вид: $f = 14a_1a_2a_3a_4a_541$, где $a_1, a_2, a_3, a_4, a_5\in \{1, 2, 3, 4\}$.

Если $a_1 = 2$, то $42a_2a_3a_4a_541\in [42-_6\hspace{-.25em}-41]\Rightarrow [13-_6\hspace{-.25em}-14]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

Если $a_1 = 3$, то $43a_2a_3a_4a_541\in [43-_6\hspace{-.25em}-41]\Rightarrow [12-_6\hspace{-.25em}-14]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).
\end{proof}

\begin{lemma} \label{l6}
Не существует $4$-изящных раскрасок $8$-ветвей следующих типов:
$$12-_8\hspace{-.25em}-21, 12-_8\hspace{-.25em}-31;$$ $$13-_8\hspace{-.25em}-21.$$
\end{lemma}
\begin{proof}
1) Пусть от противного существует $f\in [12-_8\hspace{-.25em}-21]$. Тогда $f = 12a_1a_2a_3a_4a_5a_621$, где $a_1, a_2, a_3, a_4, a_5, a_6\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_5a_621$.

Если $a_2 = 1$, то $41a_3a_4a_5a_621\in [41-_6\hspace{-.25em}-21] \Rightarrow [14-_6\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

Если $a_2 = 3$, то $43a_3a_4a_5a_621\in [43-_6\hspace{-.25em}-21] \Rightarrow [12-_6\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

2) Пусть от противного существует $f\in [12-_8\hspace{-.25em}-31]$. Тогда $f$ имеет вид: $f = 12a_1a_2a_3a_4a_5a_631$, где $a_1, a_2, a_3, a_4, a_5, a_6\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_5a_631$.

Если $a_2 = 1$, то $41a_3a_4a_5a_631\in [41-_6\hspace{-.25em}-31]\Rightarrow [14-_6\hspace{-.25em}-24]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

Если $a_2 = 3$, то $43a_3a_4a_5a_631\in [43-_6\hspace{-.25em}-31]\Rightarrow [12-_6\hspace{-.25em}-24]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

3) Пусть от противного существует $f\in [13-_8\hspace{-.25em}-21]$. Тогда $f$ имеет вид: $f = 13a_1a_2a_3a_4a_5a_621$, где $a_1, a_2, a_3, a_4, a_5, a_6\in \{1, 2, 3, 4\}$, поэтому $f = 13a_1a_2a_3a_4a_5421$.

Если $a_5 = 1$, то $13a_1a_2a_3a_414\in [13-_6\hspace{-.25em}-14]\Rightarrow [13-_6\hspace{-.25em}-14]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

Если $a_5 = 3$, то $13a_1a_2a_3a_434\in [13-_6\hspace{-.25em}-34]\Rightarrow [13-_6\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).
\end{proof}

\begin{lemma} \label{l7}
Не существует $4$-изящных раскрасок $9$-ветвей следующих типов:
$$12-_9\hspace{-.25em}-14, 12-_9\hspace{-.25em}-34;$$ $$14-_9\hspace{-.25em}-34.$$    
\end{lemma}

\begin{proof}
1) Пусть от противного существует $f\in [12-_9\hspace{-.25em}-14]$. Тогда $f = 12a_1a_2a_3a_4a_5a_6a_714$, где $a_1, a_2, a_3, a_4, a_5, a_6 , a_7\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_5a_6a_714$.

Если $a_2 = 1$, то $41a_3a_4a_5a_6a_714\in [41-_7\hspace{-.25em}-14]\Rightarrow [14-_7\hspace{-.25em}-41]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

Если $a_2 = 3$, то $43a_3a_4a_5a_6a_714\in [43-_7\hspace{-.25em}-14]\Rightarrow [12-_7\hspace{-.25em}-41]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

2) Пусть от противного существует $f\in [12-_9\hspace{-.25em}-34]$. Тогда $f$ имеет вид: $f = 12a_1a_2a_3a_4a_5a_6a_734$, где $a_1, a_2, a_3, a_4, a_5, a_6, a_7\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_5a_6a_734$.

Если $a_2 = 1$, то $41a_3a_4a_5a_6a_734\in [41-_7\hspace{-.25em}-34]\Rightarrow [14-_7\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

Если $a_2 = 3$, то $43a_3a_4a_5a_6a_734\in [43-_7\hspace{-.25em}-34] \Rightarrow [12-_7\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

3) Пусть от противного существует $f\in [14-_9\hspace{-.25em}-34]$. Тогда $f$ имеет вид: $f = 14a_1a_2a_3a_4a_5a_6a_734$, где $a_1, a_2, a_3, a_4, a_5, a_6, a_7\in \{1, 2, 3, 4\}$, поэтому $f = 14a_1a_2a_3a_4a_5a_6134$.

Если $a_6 = 2$, то $14a_1a_2a_3a_4a_521\in [14-_7\hspace{-.25em}-21] \Rightarrow [14-_7\hspace{-.25em}-21]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).

Если $a_2 = 4$, то $14a_1a_2a_3a_4a_541\in [14-_7\hspace{-.25em}-41] \Rightarrow [14-_7\hspace{-.25em}-41]\neq\emptyset$, противоречие (см. таблицу~\ref{tab1}).
\end{proof}

\begin{lemma} \label{l8}
Не существует $4$-изящных раскрасок $11$-ветвей следующего типа:
$$12-_{11}\hspace{-.25em}-21.$$    
\end{lemma}

\begin{proof}
Пусть от противного существует $f\in [12-_{11}\hspace{-.25em}-21]$. Тогда $f = 12a_1a_2a_3a_4a_5a_6a_7a_8a_921$, где $a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9\in \{1, 2, 3, 4\}$, поэтому $f = 124a_2a_3a_4a_5a_6a_7a_8a_921$.

Если $a_2 = 1$, то $41a_3a_4a_5a_6a_7a_8a_921\in [41-_9\hspace{-.25em}-21] \Rightarrow [14-_9\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).

Если $a_2 = 3$, то $43a_3a_4a_5a_6a_7a_8a_921\in [43-_9\hspace{-.25em}-21] \Rightarrow [12-_9\hspace{-.25em}-34]\neq\emptyset$, противоречие (см. таблицу~\ref{tab3}).
\end{proof}

\section{4-изящные раскраски узловых компонент}

Прежде чем рассматривать 4-изящные раскраски узловых компонент деревьев $T$ с максимальной степенью вершин $\Delta = 3$, приведём необходимые определения.

Для узловой компоненты $G$ дерева $T$ две граничные вершины, лежащие в расширенной узловой компоненте $G'$ будем называть \textit{близнецами}, если смежны инцидентные им граничные рёбра.

Ясно, что при 4-изящной раскраске расширенной узловой компоненты $G'$ для близнецов должны выполняться следующие условия \textit{допустимости} раскраски: 
\begin{itemize}
    \item близнецы имеют разный цвет,
    \item если один из близнецов имеет козырный цвет 1 или 4, то другой близнец имеет ординарный цвет (см. Рис.~\ref{ris7})
\end{itemize}

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (-1.5,-2) circle (4pt);
\node[below] at (-1.5,-2) {2};
\draw (0,0) -- (-1.5,-2);
\fill (1.5,-2) circle (4pt);
\node[below] at (1.5,-2) {3};
\draw (0,0) -- (1.5,-2);

\fill (5,0) circle (4pt);
\draw (5,0) circle (9pt);
\fill (3.5,-2) circle (4pt);
\node[below] at (3.5,-2) {2};
\draw (5,0) -- (3.5,-2);
\fill (6.5,-2) circle (4pt);
\node[below] at (6.5,-2) {1};
\draw (5,0) -- (6.5,-2);
\end{tikzpicture}
\caption{Примеры допустимых раскрасок близнецов}
\label{ris7}
\end{center}
\end{figure}

\textit{Допустимым граничным условием} для расширенной узловой компоненты $G'$ будем называть такое распределение цветов на множестве всех граничных вершин компоненты $G$, при котором допустимы раскраски всех близнецов из $G'$ (см. Рис.~\ref{ris8}).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\node[above] at (-4.5,-5) {2};
\fill (-4.5,-5) circle (4pt);
\fill (-4.5,-6) circle (4pt);
\draw (-4.5,-6) circle (9pt);
\draw (-4.5,-5) -- (-4.5,-6);
\fill (-5,-7) circle (4pt);
\draw (-5,-7) -- (-4.5,-6);
\fill (-5.5,-8) circle (4pt);
\draw (-5,-7) -- (-5.5,-8);
\fill (-6,-9) circle (4pt);
\draw (-6,-9) -- (-5.5,-8);
\fill (-6.5,-10) circle (4pt);
\draw (-6.5,-10) circle (9pt);
\draw (-6,-9) -- (-6.5,-10);
\fill (-7,-11) circle (4pt);
\draw (-7,-11) -- (-6.5,-10);
\fill (-7.5,-12) circle (4pt);
\draw (-7,-11) -- (-7.5,-12);
\fill (-8,-13) circle (4pt);
\draw (-8,-13) -- (-7.5,-12);
\fill (-8.5,-14) circle (4pt);
\draw (-8.5,-14) circle (9pt);
\draw (-8,-13) -- (-8.5,-14);
\fill (-9,-15) circle (4pt);
\draw (-9,-15) -- (-8.5,-14);
\node[below] at (-9,-15) {2};
\fill (-8,-15) circle (4pt);
\draw (-8,-15) -- (-8.5,-14);
\node[below] at (-8,-15) {3};

\fill (-6,-11) circle (4pt);
\draw (-6,-11) -- (-6.5,-10);
\fill (-5.5,-12) circle (4pt);
\draw (-6,-11) -- (-5.5,-12);
\fill (-5,-13) circle (4pt);
\draw (-5,-13) -- (-5.5,-12);
\fill (-4.5,-14) circle (4pt);
\draw (-4.5,-14) circle (9pt);
\draw (-5,-13) -- (-4.5,-14);
\fill (-4,-15) circle (4pt);
\draw (-4,-15) -- (-4.5,-14);
\node[below] at (-4,-15) {2};
\fill (-5,-15) circle (4pt);
\draw (-5,-15) -- (-4.5,-14);
\node[below] at (-5,-15) {4};

\fill (-4,-7) circle (4pt);
\draw (-4,-7) -- (-4.5,-6);
\fill (-3.5,-8) circle (4pt);
\draw (-4,-7) -- (-3.5,-8);
\fill (-3,-9) circle (4pt);
\draw (-3,-9) -- (-3.5,-8);
\fill (-2.5,-10) circle (4pt);
\draw (-2.5,-10) circle (9pt);
\draw (-3,-9) -- (-2.5,-10);
\fill (-2,-11) circle (4pt);
\draw (-2,-11) -- (-2.5,-10);
\fill (-1.5,-12) circle (4pt);
\draw (-2,-11) -- (-1.5,-12);
\fill (-1,-13) circle (4pt);
\draw (-1,-13) -- (-1.5,-12);
\fill (-.5,-14) circle (4pt);
\draw (-.5,-14) circle (9pt);
\draw (-.5,-14) -- (-1.5,-12);
\fill (0,-15) circle (4pt);
\draw (-.5,-14) -- (0,-15);
\node[below] at (0,-15) {3};
\fill (-1,-15) circle (4pt);
\draw (-.5,-14) -- (-1,-15);
\node[below] at (-1,-15) {2};

\fill (-3,-11) circle (4pt);
\draw (-3,-11) -- (-2.5,-10);
\node[below] at (-3,-11) {1};
\end{tikzpicture}
\caption{Пример допустимого граничного условия для расширенной 3-компоненты}
\label{ris8}
\end{center}
\end{figure}

\begin{theorem} \label{t1}
Для любой расширенной узловой $s$-компоненты $G'$ узловой $s$-компоненты $G$ дерева $T$ с максимальной степенью вершин $\Delta = 3$, где $s\geq 10$ и $s\neq 11$, существует такая $4$-изящная раскраска, при которой все граничные вершины раскрашены в соответствии с предварительно заданным допустимым граничным условием.
\end{theorem}

\begin{proof}
Воспользуемся тем, что для таких $s$ в силу леммы~\ref{l1} граф $s$-переходов является полным двудольным графом вида $K_{6, 6}$. Построим алгоритм нахождения 4-изящной раскраски расширенной узловой $s$-компоненты $G'$, отвечающей узловой $s$-компоненте $G$ для фиксированного числа $s\geq 10$ и $s\neq 11$. При построении раскраски для $G'$ будем использовать поиск в глубину в графе узлов и $s$-ветвей $\widetilde{G}$, вершинами которого являются узлы из $G$, а ребрами --- $s$-ветви, соединяющие узлы из $G$.

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

Зафиксируем некоторую граничную вершину $v$ компоненты $G$ и будем рассматривать $G'$ в качестве корневого дерева с корнем $v$. Будем раскрашивать $G'$, начиная с вершины $v$. Через $u$ обозначим узел из $G$, который соединяется граничным ребром с корнем $v$. Граф $\widetilde{G}$ также будем рассматривать в виде корневого дерева с корнем $u$, поиск в глубину в $\widetilde{G}$ будем проводить из узла $u$.

Опишем теперь алгоритм 4-изящной раскраски для $G'$.

\begin{enumerate}
    \item Раскрасим узел $u$ и три смежные с ним вершины таким образом, чтобы были использованы все четыре краски 1, 2, 3, 4, граничные вершины раскрашены в соответствии с допустимым граничным условием и вершина $u$ раскрашена в козырный цвет. Очевидно такая раскраска существует, зафиксируем ее.

    Узел $u$ поместим в стек $S$.
    \item Пусть $w$ --- первая вершина в стеке $S$. (Отметим, что узел $w$ и смежные с ним вершины из $G'$ ранее при работе алгоритма раскрашены в четыре разных цвета).\label{y2}
    \item Если имеется хотя бы одна не раскрашенная $s$-ветвь, выходящая из $w$, то выбираем такую $s$-ветвь. \label{y3}

    Пусть $w'$ --- финальный узел выбранной $s$-ветви с началом в узле $w$.

    Раскрасим узел $w'$ и три смежные с ним вершины таким образом, чтобы были использованы все четыре краски 1, 2, 3, 4, граничные вершины раскрашены в соответствии с допустимым граничным условием и вершина $u$ раскрашена в козырный цвет. Очевидно такая раскраска существует, зафиксируем ее.

    В таблицах~\ref{tab1},  \ref{tab2} или \ref{tab3} подберём 4-изящное слово для 4-изящной раскраски рассматриваемой $s$-ветви. 

    Для подбора такого слова берём 2-префикс, состоящий из краски, в которую окрашен узел $w$, и краски, в которую окрашена вторая вершина выбранной $s$-ветви (она смежна $w$ и окрашена раньше). В качестве 2-суффикса берем краску, в которую окрашена предпоследняя вершина рассматриваемой $s$-ветви (эта вершина смежна $w'$ и поэтому уже окрашена) и затем краску, в которую окрашен узел $w'$. В силу леммы~\ref{l1} в таблицах имеется такое 4-изящное слово длины $s + 2$. Раскрашиваем рассматриваемую $s$-ветвь в такое слово (раскрашенная часть $G'$ будет 4-изящно раскрашена).

    После этого узел $w'$ помещаем в стек $S$ и переходим к выполнению шага (\ref{y2}).
    \item Если не имеется не раскрашенных $s$-ветвей, выходящих из $w$, то 
    \begin{itemize}
        \item в случае $w\neq u$ удаляем $w$ из стека $S$ (т.\,е. возвращаемся от узла $w$ к предшествующему ему узлу в процедуре поиска в глубину) и переходим к выполнению шага (\ref{y2});
        \item в случае $w = u$ убираем $w$ из стека $S$ (стек становится пустым и найдена 4-изящная раскраска для $G'$) и Stop.
    \end{itemize}
\end{enumerate}
Очевидно, процесс раскраски вершин обязательно завершится и будет построена 4-изящная раскраска для $G'$.
\end{proof}

\textit{Слабым допустимым граничным условием} для расширенной узловой компоненты $G'$ будем называть такое распределение цветов на множестве всех граничных вершин из $G'$, при котором допустимы раскраски всех близнецов из $G'$ и в случае козырных красок в граничном условии указан лишь их \textit{козырный тип} $t$ (в дальнейшем \textit{тип ординарных} раскрасок будем обозначать через $o$), а не конкретный цвет 1 или 4 (см. Рис.~\ref{ris9}).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\node[above] at (-4.5,-5) {2};
\fill (-4.5,-5) circle (4pt);
\fill (-4.5,-6) circle (4pt);
\draw (-4.5,-6) circle (9pt);
\draw (-4.5,-5) -- (-4.5,-6);
\fill (-5,-7) circle (4pt);
\draw (-5,-7) -- (-4.5,-6);
\fill (-5.5,-8) circle (4pt);
\draw (-5,-7) -- (-5.5,-8);
\fill (-6,-9) circle (4pt);
\draw (-6,-9) -- (-5.5,-8);
\fill (-6.5,-10) circle (4pt);
\draw (-6.5,-10) circle (9pt);
\draw (-6,-9) -- (-6.5,-10);
\fill (-7,-11) circle (4pt);
\draw (-7,-11) -- (-6.5,-10);
\fill (-7.5,-12) circle (4pt);
\draw (-7,-11) -- (-7.5,-12);
\fill (-8,-13) circle (4pt);
\draw (-8,-13) -- (-7.5,-12);
\fill (-8.5,-14) circle (4pt);
\draw (-8.5,-14) circle (9pt);
\draw (-8,-13) -- (-8.5,-14);
\fill (-9,-15) circle (4pt);
\draw (-9,-15) -- (-8.5,-14);
\node[below] at (-9,-15) {2};
\fill (-8,-15) circle (4pt);
\draw (-8,-15) -- (-8.5,-14);
\node[below] at (-8,-15) {3};

\fill (-6,-11) circle (4pt);
\draw (-6,-11) -- (-6.5,-10);
\fill (-5.5,-12) circle (4pt);
\draw (-6,-11) -- (-5.5,-12);
\fill (-5,-13) circle (4pt);
\draw (-5,-13) -- (-5.5,-12);
\fill (-4.5,-14) circle (4pt);
\draw (-4.5,-14) circle (9pt);
\draw (-5,-13) -- (-4.5,-14);
\fill (-4,-15) circle (4pt);
\draw (-4,-15) -- (-4.5,-14);
\node[below] at (-4,-15) {$t$};
\fill (-5,-15) circle (4pt);
\draw (-5,-15) -- (-4.5,-14);
\node[below] at (-5,-15) {2};

\fill (-4,-7) circle (4pt);
\draw (-4,-7) -- (-4.5,-6);
\fill (-3.5,-8) circle (4pt);
\draw (-4,-7) -- (-3.5,-8);
\fill (-3,-9) circle (4pt);
\draw (-3,-9) -- (-3.5,-8);
\fill (-2.5,-10) circle (4pt);
\draw (-2.5,-10) circle (9pt);
\draw (-3,-9) -- (-2.5,-10);
\fill (-2,-11) circle (4pt);
\draw (-2,-11) -- (-2.5,-10);
\fill (-1.5,-12) circle (4pt);
\draw (-2,-11) -- (-1.5,-12);
\fill (-1,-13) circle (4pt);
\draw (-1,-13) -- (-1.5,-12);
\fill (-.5,-14) circle (4pt);
\draw (-.5,-14) circle (9pt);
\draw (-.5,-14) -- (-1.5,-12);
\fill (0,-15) circle (4pt);
\draw (-.5,-14) -- (0,-15);
\node[below] at (0,-15) {3};
\fill (-1,-15) circle (4pt);
\draw (-.5,-14) -- (-1,-15);
\node[below] at (-1,-15) {$t$};

\fill (-3,-11) circle (4pt);
\draw (-3,-11) -- (-2.5,-10);
\node[below] at (-3,-11) {$t$};
\end{tikzpicture}
\caption{Пример слабого допустимого граничного условия для расширенной 3-компоненты}
\label{ris9}
\end{center}
\end{figure}

\begin{theorem}\label{t2}
Для любой расширенной узловой $s$-компоненты $G'$ узловой $s$-компоненты $G$ дерева $T$ с максимальной степенью вершин $\Delta = 3$, где $s = 4, 6, 7, 8, 9, 11$, существует такая её $4$-изящная раскраска, при которой все граничные вершины раскрашены в соответствии с предварительно заданным слабым допустимым граничным условием.    
\end{theorem}

\begin{proof}
Воспользуемся тем, что для таких $s$ в силу лемм~\ref{l2} и \ref{l3}, а также двойственных к ним лемм, граф $s$-переходов содержит полные двудольные подграфы вида $K_{3, 3}$ (они указаны в леммах).

Построим теперь алгоритм нахождения 4-изящной раскраски расширенной узловой $s$-компоненты $G'$, отвечающей узловой $s$-компоненте $G$ для фиксированного числа $s = 4, 6, 7, 8, 9, 11$, аналогичный алгоритму, указанному в доказательстве теоремы~\ref{t1}. При построении раскраски для $G'$ будем использовать поиск в глубину в графе узлов и $s$-ветвей $\widetilde{G}$, отвечающему узловой $s$-компоненте $G$.

Алгоритм строится совершенно аналогично предыдущему, за исключением действий в (\ref{y3}). Теперь мы вынуждены выбирать цвет очередного узла $w'$ в зависимости от козырного цвета $t_1$ узла $w$, который стоит в начале выбранной $s$-ветви, которая при поиске в ширину приводит к узлу $w'$ ($w'$ стоит в конце этой $s$-ветви). Сначала по цвету $t_1$ узла $w$ в двудольном графе $s$-переходов мы выбираем тот полный двудольный подграф вида $K_{3, 3}$, в первой доле которого фигурирует цвет $t_1$, а затем берем цвет $t_2$, который фигурирует во второй доле выбранного полного двудольного графа $K_{3, 3}$.  Заметим, что при $s = 4, 7, 8, 11$ козырный цвет изменится при переходе от $t_1$ к $t_2$, т.\,е. $t_1\neq t_2$, а при $s = 6, 9$ он сохранится, т.\,е. $t_1 = t_2$. Поэтому для граничных вершин, в случае необходимости, мы можем гарантировать раскраску их в какой-то козырный цвет в соответствии со слабым допустимым граничным условием. С ординарными красками проблем нет --- с их выбором все происходит точно также, как в алгоритме из теоремы~\ref{t1}.
\end{proof}

Задача 4-изящного раскрашивания узловых $s$-компонент при $s = 1$, 2, 3, 5 значительно сложнее рассмотренных случаев для $s$. Такие компоненты могут задавать \textit{запрещённые конфигурации} для 4-изящных деревьев, т.\,е. конфигурации, которые не могут содержаться в 4-изящных деревьях. Рассмотрению узловых $s$-компонент при $s = 1, 2, 3, 5$ будет посвящена наша следующая работа.

В заключительной части данной работы мы рассмотрим 4-изящные раскраски узловых 2-компонент дерева $T$ с максимальной степенью вершин $\Delta = 3$ и покажем, как узловые 2-компоненты могут задавать запрещённые конфигурации для 4-изящных деревьев.

\begin{lemma} \label{l9}
Любая расширенная узловая 2-компонента $G'$ узловой 2-компоненты $G$ дерева $T$ с максимальной степенью вершин $\Delta = 3$ не имеет 4-изящных раскрасок таких, что все граничные вершины компоненты $G$ имеют ординарный цвет.    
\end{lemma}

\begin{proof}
Пусть от противного расширенная узловая 2-ком\-по\-нен\-та $G'$ имеет 4-изящную раскраску такую, что все граничные вершины узловой 2-компоненты $G$ имеют ординарный цвет. Зафиксируем некоторую такую раскраску для $G'$.

В $G$ зафиксируем также узел $v$, который является висячей вершиной в дереве узлов и 2-ветвей $\widetilde{G}$. Без ограничения общности с учетом двойственности для 4-изящных раскрасок будем считать, что $v$ имеет цвет 1. Ясно, что у вершины $v$ имеются две смежные с ней граничные вершины $u_1$ и $u_2$ узловой 2-компоненты $G$. Они являются близнецами и имеют различные ординарные цвета (их ординарный тип на рисунках мы договорились обозначать через $o$). Тогда третья вершина $w_1$, смежная с узлом $v$, имеет цвет 4. Поскольку все граничные вершины узловой 2-компоненты $G$ имеют ординарные цвета, вершина $w_1$ не является граничной вершиной. Следовательно, она принадлежит некоторой 2-ветви $v$, $w_1$, $x_1$, $v_1$, выходящей из узла $v$ и входящей в узел $v_1$. Так как вершина $w_1$ имеет цвет 4, узел $v_1$ имеет цвет 1, а вершина $x_1$ имеет ординарный цвет.

Узел $v_1$, кроме вершины $x_1$, имеет ещё две смежные вершины $y_2$, $w_2$. Без ограничения общности будем считать, что вершина $y_2$ имеет ординарный цвет, а вершина $w_2$ имеет цвет 4. Поэтому вершина $w_2$ не является граничной, следовательно, она принадлежит некоторой 2-ветви $v_1$, $w_2$, $x_2$, $v_2$ узловой 2-компоненты $G$.

Продолжаем указанный процесс построения 2-ветвей в узловой 2-ком\-по\-нен\-те $G$. Поскольку $G'$ --- дерево, повторения вершин не произойдёт, будет строиться поддерево дерева $G'$ (см. Рис.~\ref{ris10}).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (-2,2) circle (4pt);
\node[below] at (-2,2) {$o$};
\draw (0,0) -- (-2,2);
\fill (-2,-2) circle (4pt);
\node[below] at (-2,-2) {$o$};
\draw (0,0) -- (-2,-2);

\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[above] at (0,0.2) {$v$};
\node[below] at (0,-0.2) {$1$};
\fill (2,0) circle (4pt);
\node[above] at (2,0) {$w_1$};
\node[below] at (2,0) {$4$};
\draw (0,0) -- (2,0);
\fill (4,0) circle (4pt);
\node[above] at (4,0) {$x_1$};
\node[below] at (4,0) {$o$};
\draw (2,0) -- (4,0);
\draw (4,0) -- (6,0);
\fill (6,0) circle (4pt);
\draw (6,0) circle (9pt);
\node[above] at (6,0.2) {$v_1$};
\node[below] at (6,-0.2) {$1$};
\draw (6,0) -- (8,0);
\fill (8,0) circle (4pt);
\node[above] at (8,0) {$w_2$};
\node[below] at (8,0) {$4$};
\draw (8,0) -- (10,0);
\fill (10,0) circle (4pt);
\node[above] at (10,0) {$x_2$};
\node[below] at (10,0) {$o$};
\fill (12,0) circle (4pt);
\draw (12,0) circle (9pt);
\node[above] at (12,0.2) {$v_2$};
\node[below] at (12,-0.2) {$1$};
\draw (12,0) -- (10,0);
\fill (14,0) circle (4pt);
\node[below] at (14,0) {$4$};
\draw (12,0) -- (14,0);
\fill (16,0) circle (4pt);
\node[below] at (16,0) {$o$};
\draw (16,0) -- (14,0);
\fill (18,0) circle (4pt);
\draw (18,0) circle (9pt);
\node[below] at (18,-0.2) {$1$};
\draw (16,0) -- (18,0);
\node at (19.2,0) {$\dots$};

\fill (8,-2) circle (4pt);
\node[below] at (8,-2) {$o$};
\node[above right] at (8,-2.4) {$y_2$};
\draw (6,0) -- (8,-2);
\fill (14,-2) circle (4pt);
\node[below] at (14,-2) {$o$};
\draw (12,0) -- (14,-2);
\end{tikzpicture}
\caption{Поддерево дерева $G'$}
\label{ris10}
\end{center}
\end{figure}

На некотором шаге построения строящееся поддерево будет содержать вершин больше чем дерево $G'$, пришли к противоречию.
\end{proof}

Будем говорить, что узловая 2-компонента является \textit{изолированной} (см. Рис.~\ref{ris11}), если любая её граничная вершина \textit{изолирована}, т.\,е. смежна некоторому узлу, не принадлежащему этой компоненте (будем говорить, что этот узел и инцидентное ему ребро, ведущее к граничной вершине, \textit{изолируют} граничную вершину).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,1) circle (4pt);
\draw (0,0) -- (0,1);
\fill (0,2) circle (4pt);
\draw (0,2) circle (9pt);
\draw (0,2) -- (0,1);

\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\fill (0.5,-1) circle (4pt);
\draw (0,0) -- (0.5,-1);
\fill (1,-2) circle (4pt);
\draw (0.5,-1) -- (1,-2);
\fill (1.5,-3) circle (4pt);
\draw (1.5,-3) circle (9pt);
\draw (1,-2) -- (1.5,-3);
\fill (2,-4) circle (4pt);
\draw (1.5,-3) -- (2,-4);
\fill (2.5,-5) circle (4pt);
\draw (2.5,-5) -- (2,-4);
\fill (2,-2) circle (4pt);
\draw (1.5,-3) -- (2,-2);
\fill (2.5,-1) circle (4pt);
\draw (2.5,-1) circle (9pt);
\draw (2.5,-1) -- (2,-2);
\fill (3,-6) circle (4pt);
\draw (3,-6) circle (9pt);
\draw (2.5,-5) -- (3,-6);
\fill (3.5,-7) circle (4pt);
\draw (3.5,-7) -- (3,-6);
\fill (4,-8) circle (4pt);
\draw (4,-8) circle (9pt);
\draw (3.5,-7) -- (4,-8);
\fill (2.5,-7) circle (4pt);
\draw (2.5,-7) -- (3,-6);
\fill (2,-8) circle (4pt);
\draw (2,-8) circle (9pt);
\draw (2.5,-7) -- (2,-8);

\fill (-0.5,-1) circle (4pt);
\draw (0,0) -- (-0.5,-1);
\fill (-1,-2) circle (4pt);
\draw (-0.5,-1) -- (-1,-2);
\fill (-1.5,-3) circle (4pt);
\draw (-1.5,-3) circle (9pt);
\draw (-1,-2) -- (-1.5,-3);

\fill (-2,-4) circle (4pt);
\draw (-1.5,-3) -- (-2,-4);
\fill (-2.5,-5) circle (4pt);
\draw (-2,-4) -- (-2.5,-5);
\fill (-3,-6) circle (4pt);
\draw (-3,-6) circle (9pt);
\draw (-2.5,-5) -- (-3,-6);
\fill (-3.5,-7) circle (4pt);
\draw (-3,-6) -- (-3.5,-7);
\fill (-4,-8) circle (4pt);
\draw (-4,-8) circle (9pt);
\draw (-3.5,-7) -- (-4,-8);
\fill (-2.5,-7) circle (4pt);
\draw (-3,-6) -- (-2.5,-7);
\fill (-2,-8) circle (4pt);
\draw (-2,-8) circle (9pt);
\draw (-2.5,-7) -- (-2,-8);

\fill (-1,-4) circle (4pt);
\draw (-1.5,-3) -- (-1,-4);
\fill (-.5,-5) circle (4pt);
\draw (-1,-4) -- (-.5,-5);
\fill (0,-6) circle (4pt);
\draw (0,-6) circle (9pt);
\draw (-.5,-5) -- (0,-6);
\fill (.5,-7) circle (4pt);
\draw (0,-6) -- (.5,-7);
\fill (1,-8) circle (4pt);
\draw (1,-8) circle (9pt);
\draw (.5,-7) -- (1,-8);
\fill (-.5,-7) circle (4pt);
\draw (0,-6) -- (-.5,-7);
\fill (-1,-8) circle (4pt);
\draw (-1,-8) circle (9pt);
\draw (-.5,-7) -- (-1,-8);
\draw[line width=.5pt, color=red] (-.5,0) arc[start angle=180, end angle=0, radius=0.5cm] -- (3.5,-6) arc[start angle=0, end angle=-90, radius=0.5cm] -- (-3,-6.5) arc[start angle=270, end angle=180, radius=0.5cm] -- cycle;
\end{tikzpicture}
\caption{Пример изолированной узловой 2-компоненты}
\label{ris11}
\end{center}
\end{figure}

Из леммы~\ref{l9} очевидно вытекает следующая

\begin{theorem} \label{t3}
Дерево, обладающее 4-изящной раскраской, не имеет изолированных узловых 2-компонент.    
\end{theorem}

Эта теорема говорит о том, что изолированные узловые 2-компоненты являются примерами запретных конфигураций для 4-изящных деревьев.

\begin{lemma} \label{l10}
Любая расширенная узловая 2-компонента $G'$ узловой 2-компоненты $G$ дерева $T$ с максимальной степенью вершин $\Delta = 3$ имеет 4-изящную раскраску, в которой одна наперёд заданная граничная вершина имеет козырный цвет, а остальные граничные вершины имеют ординарные цвета.  
\end{lemma}

\begin{proof}
Дерево $G'$ представим в виде корневого дерева, причём в качестве корня возьмем и зафиксируем одну из граничных вершин $v$ узловой 2-компоненты $G$. При построении 4-изящной раскраски для $G'$ будем использовать поиск в ширину в графе узлов и 2-ветвей $\widetilde{G}$, отвечающем узловой 2-компоненте $G$.

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

Через $u$ обозначим узел из $G$, смежный с $v$. Поиск в ширину в $\widetilde{G}$ будем проводить из узла $u$.

Опишем теперь алгоритм 4-изящной раскраски для $G'$.

\begin{enumerate}
    \item Начнем с того, что раскрасим корень $v$ в цвет 4. Потом раскрасим узел $u$ из $G$, смежный с $v$, в цвет 1. Затем две вершины из $G'$, смежные с узлом $u$ и отличные от $v$, раскрасим в ординарные цвета 2 и 3 (среди этих вершин могут быть и граничные вершины). 

    Узел u поместим в очередь S.

    \item Пусть $w$ --- первая вершина в очереди $S$. (Отметим, что узел $w$ и смежные ему вершины из $G'$ ранее при работе алгоритма раскрашены в четыре разных цвета: для узлов, помещаемых в очередь на шаге (\ref{sh3}), предпоследняя вершина 2-ветви всегда окрашена в цвет 4, а остальные, смежные с узлом вершины, окрашены в ординарные цвета.) \label{sh2}

    \item Если имеется хотя бы одна не раскрашенная 2-ветвь, выходящая из $w$, то раскрашиваем выходящие из текущего узла $w$ все 2-ветви в соответствии с правилом раскраски a) или b), указанном на Рис.~\ref{ris12}. В случае a) из узла $w$ выходит одна 2-ветвь, подлежащая раскраске, в случае b) --- две таких 2-ветви. \label{sh3}

\begin{figure}[h]
\begin{minipage}[h]{0.49\linewidth}
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,2) circle (4pt);
\node[right] at (0,2) {$4$};
\draw (0,0) -- (0,2);
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[right] at (0.2,0) {$1$};
\fill (1,-2) circle (4pt);
\node[right] at (1,-2) {$3$};
\draw (0,0) -- (1,-2);

\fill (-1,-2) circle (4pt);
\node[left] at (-1,-2) {$2$};
\draw (0,0) -- (-1,-2);
\fill (-2,-4) circle (4pt);
\node[left] at (-2,-4) {$4$};
\draw (-1,-2) -- (-2,-4);
\fill (-3,-6) circle (4pt);
\draw (-3,-6) circle (9pt);
\node[left] at (-3.2,-6) {$1$};
\draw (-2,-4) -- (-3,-6);
\fill (-4,-8) circle (4pt);
\node[left] at (-4,-8) {$2$};
\draw (-3,-6) -- (-4,-8);
\fill (-2,-8) circle (4pt);
\node[right] at (-2,-8) {$3$};
\draw (-3,-6) -- (-2,-8);
\node at (0,-9.5) {a)};
\end{tikzpicture}
\end{center}
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\begin{tikzpicture}[scale=0.4]
\fill (0,2) circle (4pt);
\node[right] at (0,2) {$4$};
\draw (0,0) -- (0,2);
\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[right] at (0.2,0) {$1$};
\fill (1,-2) circle (4pt);
\node[right] at (1,-2) {$3$};
\draw (0,0) -- (1,-2);
\fill (2,-4) circle (4pt);
\node[right] at (2,-4) {$4$};
\draw (1,-2) -- (2,-4);
\fill (3,-6) circle (4pt);
\draw (3,-6) circle (9pt);
\node[right] at (3.2,-6) {$1$};
\draw (2,-4) -- (3,-6);
\fill (4,-8) circle (4pt);
\node[right] at (4,-8) {$3$};
\draw (3,-6) -- (4,-8);
\fill (2,-8) circle (4pt);
\node[left] at (2,-8) {$2$};
\draw (3,-6) -- (2,-8);

\fill (-1,-2) circle (4pt);
\node[left] at (-1,-2) {$2$};
\draw (0,0) -- (-1,-2);
\fill (-2,-4) circle (4pt);
\node[left] at (-2,-4) {$4$};
\draw (-1,-2) -- (-2,-4);
\fill (-3,-6) circle (4pt);
\draw (-3,-6) circle (9pt);
\node[left] at (-3.2,-6) {$1$};
\draw (-2,-4) -- (-3,-6);
\fill (-4,-8) circle (4pt);
\node[left] at (-4,-8) {$2$};
\draw (-3,-6) -- (-4,-8);
\fill (-2,-8) circle (4pt);
\node[right] at (-2,-8) {$3$};
\draw (-3,-6) -- (-2,-8);
\node at (0,-9.5) {b)};
\end{tikzpicture}
\end{minipage}
\caption{Два способа раскраски для текущего узла $w$}
\label{ris12}
\end{figure}
После раскраски 2-ветвей, выходящих из узла $w$, узлы, которыми заканчиваются вновь раскрашенные 2-ветви, отправляем в конец очереди и переходим к (\ref{sh2}).

\item Если не имеется не раскрашенных 2-ветвей, выходящих из $w$, то
\begin{itemize}
    \item в случае $w\neq u$ удаляем $w$ из очереди $S$ (т.\,е. возвращаемся от узла $w$ к предшествующему ему узлу в процедуре поиска в ширину) и переходим к (\ref{sh2});
    \item в случае $w = u$ убираем $w$ из очереди $S$ (очередь становится пустой и найдена 4-изящная раскраска для $G'$) и Stop.
\end{itemize}
\end{enumerate}

Очевидно, процесс раскраски вершин обязательно завершится и будет построена 4-изящная раскраска для $G'$.
\end{proof}

Рассмотрим теперь произвольную конфигурацию $H$, которая является деревом с максимальной степенью вершин $\Delta = 3$ и которая устроена следующим образом. В $H$ имеется подграф $H_1$, представляющий из себя узловую 2-компоненту, и имеются выделенные узел $w$ в $H_1$ и вершина $v$, не принадлежащая $H_1$. Все граничные вершины узловой 2-компоненты $H_1$, отличные от вершины $v$, являются изолированными в $H$. 

Иными словами, $H$ состоит из конфигурации $H_1$, которая является узловой 2-компонентой в $H$, добавленной вершины $v$, добавленных граничных вершин, добавленных узлов и рёбер, изолирующих граничные вершины, отличные от $v$ (пример такой конфигурации см. на Рис.~\ref{ris13}).


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\fill (0,1.5) circle (4pt);
\node[above] at (0,1.5) {$v$};
\draw (0,1.5) -- (0,0);

\fill (0,0) circle (4pt);
\draw (0,0) circle (9pt);
\node[right] at (0.35,0) {$w$};
\fill (0.5,-1) circle (4pt);
\draw (0,0) -- (0.5,-1);
\fill (1,-2) circle (4pt);
\draw (0.5,-1) -- (1,-2);
\fill (1.5,-3) circle (4pt);
\draw (1.5,-3) circle (9pt);
\draw (1,-2) -- (1.5,-3);
\fill (2,-4) circle (4pt);
\draw (1.5,-3) -- (2,-4);
\fill (2.5,-5) circle (4pt);
\draw (2.5,-5) -- (2,-4);
\fill (2,-2) circle (4pt);
\draw (1.5,-3) -- (2,-2);
\fill (2.5,-1) circle (4pt);
\draw (2.5,-1) circle (9pt);
\draw (2.5,-1) -- (2,-2);
\fill (3,-6) circle (4pt);
\draw (3,-6) circle (9pt);
\draw (2.5,-5) -- (3,-6);
\fill (3.5,-7) circle (4pt);
\draw (3.5,-7) -- (3,-6);
\fill (4,-8) circle (4pt);
\draw (4,-8) circle (9pt);
\draw (3.5,-7) -- (4,-8);
\fill (2.5,-7) circle (4pt);
\draw (2.5,-7) -- (3,-6);
\fill (2,-8) circle (4pt);
\draw (2,-8) circle (9pt);
\draw (2.5,-7) -- (2,-8);

\fill (-0.5,-1) circle (4pt);
\draw (0,0) -- (-0.5,-1);
\fill (-1,-2) circle (4pt);
\draw (-0.5,-1) -- (-1,-2);
\fill (-1.5,-3) circle (4pt);
\draw (-1.5,-3) circle (9pt);
\draw (-1,-2) -- (-1.5,-3);

\fill (-2,-4) circle (4pt);
\draw (-1.5,-3) -- (-2,-4);
\fill (-2.5,-5) circle (4pt);
\draw (-2,-4) -- (-2.5,-5);
\fill (-3,-6) circle (4pt);
\draw (-3,-6) circle (9pt);
\draw (-2.5,-5) -- (-3,-6);
\fill (-3.5,-7) circle (4pt);
\draw (-3,-6) -- (-3.5,-7);
\fill (-4,-8) circle (4pt);
\draw (-4,-8) circle (9pt);
\draw (-3.5,-7) -- (-4,-8);
\fill (-2.5,-7) circle (4pt);
\draw (-3,-6) -- (-2.5,-7);
\fill (-2,-8) circle (4pt);
\draw (-2,-8) circle (9pt);
\draw (-2.5,-7) -- (-2,-8);

\fill (-1,-4) circle (4pt);
\draw (-1.5,-3) -- (-1,-4);
\fill (-.5,-5) circle (4pt);
\draw (-1,-4) -- (-.5,-5);
\fill (0,-6) circle (4pt);
\draw (0,-6) circle (9pt);
\draw (-.5,-5) -- (0,-6);
\fill (.5,-7) circle (4pt);
\draw (0,-6) -- (.5,-7);
\fill (1,-8) circle (4pt);
\draw (1,-8) circle (9pt);
\draw (.5,-7) -- (1,-8);
\fill (-.5,-7) circle (4pt);
\draw (0,-6) -- (-.5,-7);
\fill (-1,-8) circle (4pt);
\draw (-1,-8) circle (9pt);
\draw (-.5,-7) -- (-1,-8);
\draw[line width=.5pt, color=red] (-.5,0) arc[start angle=180, end angle=0, radius=0.5cm] -- (3.5,-6) arc[start angle=0, end angle=-90, radius=0.5cm] -- (-3,-6.5) arc[start angle=270, end angle=180, radius=0.5cm] -- cycle;
\end{tikzpicture}
\caption{Пример замка $H$ с замочным входом $vw$ и ключами 41, 14}
\label{ris13}
\end{center}
\end{figure}

Если такая конфигурация $H$ содержится в 4-изящно раскрашенном дереве, то к ней применимы леммы~\ref{l9} и \ref{l10}, поэтому пара $vw$, где $w$ --- узел, в силу лемм~\ref{l9} и \ref{l10} имеет цвета 14 или цвета 41.

Такую конфигурацию $H$ будем называть \textit{замком с замочным входом} $vw$ и с \textit{ключами} 14, 41. Из шести возможных раскрасок 21, 31, 41, 14, 24 и 34 для пары $vw$ замка $H$ допустимы лишь раскраски 14 и 41, которые взаимно двойственны (т.\,е. с точностью до двойственности ключ единствен). Наличие замка $H$ в дереве $T$ при 4-изящной раскраске дерева $T$ накладывает на раскраску вершины $v$ жёсткое условие: вершина $v$ имеет цвет 1, если узел $w$ имеет цвет 4, и вершина $v$ имеет цвет 4, если узел $w$ имеет цвет 1.

В следующей работе будут указаны и другие виды замков с другими ключами. Будут приведены различные способы построения запрещённых конфигураций в 4-изящных деревьях с помощью замков.

В заключение отметим следующую задачу.

\textbf{Задача.} Изучить семейство запрещенных конфигураций в 4-изящных графах.
\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).
 
\bibitem{1} M. O. Asanov, V. A. Baranskii, and V. V. Rasin,
{\it Discrete Mathematics: Graphs, Matroids, Algorithms}, Publ. Lan’, 2010 [in Russian].

\bibitem{2} V.A.~Baransky, I.A.~Nasyrov, T.A.~Senchonok,
\href{https://doi.org/10.21538/0134-4889-2024-30-4-64-76}{\it 4-graceful trees}, Trudy Inst. Mat. Mekh. UrO RAN, \textbf{30}:4 (2024), 34--47 [in Russian].

\bibitem{3} G.~Chartrand, P.~Zhang,
{\it Chromatic Graph Theory. Discrete Mathematics and Its Applications}, Chapman and Hall/CRC Press, Boca Raton, 2009.

\bibitem{4} J.A.~Gallian, 
\href{https://doi.org/10.37236/27} {\it A dynamic survey of graph labeling}, Electron. J. Comb. DS6, Dynamic Surveys (electronic only) (1998), 43 pages.

\bibitem{5} E.~English, P.~Zhang, 
\href{https://doi.org/10.21136/MB.2017.0035-15} {\it On graceful colorings of trees}, MATHEMATICA BOHEMIC, \textbf{142}:1 (2016), 57--73.

\bibitem{6} A.D.~Byers, 
\href{https://scholarworks.wmich.edu/dissertations/3308}{\it Graceful Colorings and Connection in Graphs}, Diss. Doct. at Western Michigan University, 2018. Dissertations. 3308.

\bibitem{7} I.N.~Suparta, M.~Venkathacalam, A.I.~Gunadi Gede, A.C.~Pratama Putu, \href{http://dx.doi.org/10.15826/umj.2023.2.016} {\it Graceful chromatic number of some Cartesian product graphs} Ural Math. J., \textbf{9}:2 (2023), 193--208.

\bibitem{8} D.~Laavanya, S.~Devi Yamini, 
\href{https://www.sciencedirect.com/science/article/pii/S2405844023067713} {\it A structural approach to the graceful coloring of a subclass of tree} Helion, \textbf{9}:9 (2023), 10 pages.

\end{thebibliography}
\end{document}
