\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{array}
\usepackage[colorlinks]{hyperref}
\usepackage{tikz}
%\usetikzlibrary{arrows.meta,decorations.markings}










\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{???.??} %Здесь автор определяет УДК своей работы
\def\mscs{??X??} %Здесь автор определяет классификаторы 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 Экстремальные  ориентации циркулянтных графов]{\large Экстремальные эйлеровы ориентации циркулянтных графов }
\author[С.В. АВГУСТИНОВИЧ и др.
%, И.С. БЫКОВ, А.Л. ПЕРЕЖОГИН, А.С. КРИВОНОГОВА
]{{\bf \large \textsc{С.В. Августинович, И.С. Быков, А.Л. Пережогин, А.С. Кривоногова}}
%\protect\orcidicon{0000-0001-8827-2630}
\\ \\
\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%

\address{Sergei Vladimirovich Avgustinovich   % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{avgust@math.nsc.ru}}%

\address{Igor Sergeevich Bykov   % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{iii} Novosibirsk State University,
	\newline\hphantom{iii} Pirogova str., 1,
	\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{igor.s.bykov@yandex.ru}}%


	\address{Aleksei L’vovich Perezhogin  % Контактные данные всех авторов и место работы указываются только на английском языке
		\newline\hphantom{iii} Sobolev Institute of Mathematics,
		\newline\hphantom{iii} pr. Koptyuga, 4,
		\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
	\email{\textcolor{blue}{pereal@math.nsc.ru}}%

	\address{Alena Sergeevna Krivonogova  % Контактные данные всех авторов и место работы указываются только на английском языке
		\newline\hphantom{iii} Novosibirsk State University,
		\newline\hphantom{iii} Pirogova str., 1,
		\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
	\email{\textcolor{blue}{k.alena.s.610@gmail.com}}%


\thanks{\sc Avgustinovich, S.V., Bykov, I.S., Perezhogin, A.L., Krivonogova A.S.
Extreme Eulerian orientations of circulant graphs}
\thanks{\copyright \ 2023 Августинович С.В., Быков И.С., Пережогин А.Л., Кривоногова А.С. }
\thanks{\rm Исследование выполнено в рамках государственного задания ИМ СО РАН (проект
№ FWNF-2022-0017)}
\thanks{\it Поступила 1 января 2024 г., опубликована 31 декабря 2024 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:}
In this paper, we consider the achievability of the maximum and minimum numbers of
occurrences of 3-circuits in Eulerian orientations of complete graphs missing a transitive
subset of edges: complete graphs with an even number of vertices and a perfect matching
removed, and those with an odd number of vertices and a Hamiltonian cycle removed. For
each of these families of digraphs, we obtain upper and lower estimates for the number of 3-circuits and prove their achievability. Previously, orientations that are extreme with respect
to the number of 4-circuit occurrences have been investigated in
\cite{Per}.



\medskip

\noindent{\bf Keywords:} Eulerian orientation of graph, circuit, tournament.
 \end{quote}
}

\bigskip

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

В самом общем виде рассматриваемая задача формулируется следующим образом.
Для произвольного семейства графов (в нашем случае – ориентированных эйлеровых) определить, на каких представителях семейства достигает максимума или минимума число вхождений некоторого фиксированного фрагмента (например, 3-контура).
Довольно часто удается не только найти значение этого экстремума, но и охарактеризовать те графы, на которых он достигается \cite{Per}. Экстремальные графы при этом обычно обладают характерными свойствами совершенных структур \cite{Kir1, Tar} и получаются друг из друга свитчингами. Минимальными нетривиальными фрагментами являются трехвершинные. В неориентированном случае они изучались в \cite{PCh, PLy}.


Ориентацией графа $G$ назовем орграф, получаемый из $G$ заменой каждого ребра $vu$ на ровно одну из дуг $vu$ или $uv$. Две ориентации одного графа назовем эквивалентными, если изоморфны соответствующие орграфы. Ориентация полного графа называется турниром. Ориентация графа $G$ называется эйлеровой, если в каждой вершине полустепень исхода равна полустепени захода. Для связного графа $G$ существует эйлерова ориентация тогда и только тогда, когда $G$ является эйлеровым. Через $O(G)$ обозначим множество всех эйлеровых ориентаций графа $G$. Например, $O(K_{2n+1})$ --- это множество эйлеровых турниров на $(2n+1)$-ой вершине.

Любые три вершины произвольного турнира либо образуют ориентированный 3-цикл (контур), либо антиконтур. Хорошо известно, что   число 3-контуров в произвольном турнире однозначно определено набором полустепеней исхода и захода вершин этого графа \cite{Per}. Это, в частности, означает, что в эйлеровых турнирах число 3-контуров не зависит от выбора турнира. Для произвольной дуги $e$ орграфа $H$ обозначим через $f_a(H,e)$ количество 3-контуров, проходящих через нее. Данный инвариант зачастую позволяет разбить все дуги турнира на орбиты (классы эквивалентности) относительно его группы автоморфизмов. В работе охарактеризованы классы эйлеровых ориентаций некоторых графов, на которых функция $f_a(H,e)$ достигает экстремальных распределений по дугам $H$.

Ранее исследовались ориентации, экстремальные
по числу вхождений 4-контуров \cite{Per}. Также представляет интерес экстремальное поведение неориентированных графов
с фиксированным числом ребер и максимальным числом вхождений индуцированных $K_{1,2}$ \cite{PLy}.

В работе изучаются минимальные и максимальные распределения
3-контуров, проходящих через различные множества дуг произвольного эйлерова турнира. Доказано, что среди эйлеровых ориентаций  полного графа с удаленным гамильтоновым циклом максимальное число 3-контуров достигается с точностью до эквивалентности на циркулянтной ориентации, в которой гамильтонов цикл расположен на периферии графа, а все дуги ориентированы по часовой  стрелке. Для полного графа с четным числом вершин и удаленным паросочетанием получен аналогичный результат. Паросочетание в этом случае состоит из ребер, соединяющих диаметрально противоположные вершины, а максимум и минимум числа 3-контуров достигается сразу на целых семействах ориентаций.



\section{Ориентации циркулянтов}

%Согласно \cite{Per} через $a$ обозначим 3-контур, а через $A$, $B$, $C$ и $D$  все ориентации 4-цикла (Рис. \ref{cicle4}).
%
%	\begin{figure}
%		\begin{center}
%\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]%
%\draw[-latex,thick](0,0)node
%        {$$} to[out=90,in=-90] (0,2);
%\draw[-latex,thick](0,2)node
%        {$$} to[out=0,in=180] (2,2);
%\draw[-latex,thick](2,2)node
%        {$$} to[out=-90,in=90] (2,0);
%\draw[-latex,thick](2,0)node
%        {$$} to[out=180,in=0] (0,0);
%\draw[-latex,thick](3,0)node
%        {$$} to[out=90,in=-90] (3,2);
%\draw[-latex,thick](3,2)node
%        {$$} to[out=0,in=180] (5,2);
%\draw[-latex,thick](5,2)node
%        {$$} to[out=-90,in=90] (5,0);
%\draw[-latex,thick](3,0)node
%        {$$} to[out=0,in=180] (5,0);
%\draw[-latex,thick](6,0)node
%        {$$} to[out=90,in=-90] (6,2);
%\draw[-latex,thick](6,2)node
%        {$$} to[out=0,in=180] (8,2);
%\draw[-latex,thick](8,0)node
%        {$$} to[out=90,in=-90] (8,2);
%\draw[-latex,thick](6,0)node
%        {$$} to[out=0,in=180] (8,0);
%\draw[-latex,thick](9,0)node
%        {$$} to[out=90,in=-90] (9,2);
%\draw[-latex,thick](11,2)node
%        {$$} to[out=180,in=0] (9,2);
%\draw[-latex,thick](11,2)node
%        {$$} to[out=-90,in=90] (11,0);
%\draw[-latex,thick](9,0)node
%        {$$} to[out=0,in=180] (11,0);
%\large
%
%\coordinate [label=above:\textcolor{black}{$A$}] (B) at (1,-0.6);
%\coordinate [label=above:\textcolor{black}{$B$}] (B) at (4,-0.6);
%\coordinate [label=above:\textcolor{black}{$C$}] (B) at (7,-0.6);
%\coordinate [label=above:\textcolor{black}{$D$}] (B) at (10,-0.6);
%
%\end{tikzpicture}%\hspace{1cm}
%			\caption{Типы ориентаций 4-циклов.}\label{cicle4}
%		\end{center}
%	\end{figure}

% Обозначим через $f_\lambda(H)$ количество вхождений конфигурации типа $\lambda$ в орграф $H$.
Согласно \cite{Per} через  $f_a(H)$ обозначим количество 3-контуров в орграфе $H$.

Обозначим через  $K_{2n}\setminus M$ полный граф с удаленным совершенным паросочетанием, а через $K_{2n+1}\setminus C$ полный граф с удаленным гамильтоновым циклом.

Выходящей окрестностью $N^+(v)$ вершины $v$ в ориентации $H$ графа $G$ будем называть множество вершин, в которые ведут дуги, начинающиеся в $v$. Аналогично определяется входящая окрестность $N^-(v)$. Для любой дуги $e=uv$ орграфа $H$ имеем
\begin{equation}\label{okr}
f_a(H,e)=|N^+(v)\cap N^-(u)|.
\end{equation}

\begin{proposition}
Для любой дуги $e$ эйлеровой ориентации $T\in O(K_{2n+1})$ верны неравенства
\begin{equation}\label{eq01}
1\le f_a(T,e)\le n.
\end{equation}

\end{proposition}
\begin{proof}
Пусть $e=uv$. Верхняя оценка следует из равенства
$$|N^+(v)|=|N^-(u)|=n.$$
Для доказательства нижней оценки остается заметить, что
\begin{equation}
 |N^+(v)\cup N^-(u)|\le |V(T)\setminus\{v,u\}|=2n-1.
\end{equation}
\end{proof}

\begin{proposition}\label{modu}
Если для дуги $e=uv$ эйлеровой ориентации $T\in O(K_{2n+1})$ имеем $f_a(T,e)=1$, то справедливы равенства
$$|N^+(v)\cap N^+(u)|=|N^-(v)\cap N^-(u)|=n-1.$$
\end{proposition}
\begin{proof}
Поскольку $|N^+(v)\cap N^-(u)|=1$, то $|N^+(v)\cup N^-(u)|=2n-1.$
\end{proof}

Согласно \cite{Per} количество 3-контуров в произвольной эйлеровой ориентации  $T\in O(K_{2n+1})$ равно \begin{equation}\label{tra}
  f_a(T)=\frac{2n+1}{3}\binom{n+1}{2}.
\end{equation}

Из (\ref{tra}) непосредственно следует следующее утверждение.

\begin{proposition}
Для любой эйлеровой ориентации $T\in O(K_{2n+1})$ верно
\begin{equation}\label{eq02}
\sum_{e\in T} f_a(T,e)=(2n+1)\binom{n+1}{2}.
\end{equation}
\end{proposition}

Через $C_{N}(d_1,\ldots,d_p)$, $0<d_1<\cdots<d_p<N/2$, обозначим неориентированный циркулянтный граф на $N$ вершинах $\{0,\ldots,N-1\}$, в котором две вершины $i$ и $j$ соединены ребром тогда и только тогда, когда
$$\min (|i-j|,N-|i-j|)\in \{d_1,\ldots,d_p\}.$$
Иными словами, если вершины расположить по циклу, то ребром соединяем вершины, между которыми расстояние по циклу (расстояние) равно $d_k$ для некоторого $k$.

Через $C_{N}(d_1,\ldots,d_p;t_1,\ldots,t_p)$, $t_i\in \{-1,+1\}$, обозначим  эйлерову ориентацию графа $C_{N}(d_1,\ldots,d_p)$, в которой дуга между вершинами на расстоянии  $d_k$ ориентирована по часовой стрелке, если $t_k=+1$, и против часовой стрелки, если $t_k=-1$.
Заметим, что
$$C_{2n+1}(1,\ldots,n;t_1,\ldots,t_n) \in O(K_{2n+1}),$$
$$C_{2n}(1,\ldots,n-1;t_1,\ldots,t_{n-1}) \in O(K_{2n} \setminus M).$$

\begin{proposition}\label{Li} Для $T=C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$ значения $f_a(T,e)$  на каждой дуге $e$, соединяющей вершины на расстоянии  $p$, принимает значение $p$.
\end{proposition}
Это легко следует из простого факта, что число целочисленных решений уравнения $x+y+z=2n+1$ при фиксированных $x$ и $n$ с ограничением $0<y,z\leq n$ равно $x$.

\section{Турниры с выделенным гамильтоновым циклом}

В данном разделе дается характеризация турниров, у которых ребрам некоторого гамильтонова контура соответствует экстремальное значение параметра $f_a(T,e)$.
\begin{theorem}\label{theor1} Пусть в турнире $T\in O(K_{2n+1})$  для каждой дуги $e$ некоторого гамильтонова контура значение $f_a(T,e)$ равно 1. Тогда выполняется $T\simeq C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$.
\end{theorem}
\begin{proof}
Рассмотрим  гамильтонов контур $C=v_0,v_1,\ldots,v_{2n}$ такой, что $$f_a(T,v_iv_{i+1})=1,\ \ 0\le i\le 2n.$$
Здесь и далее индексы берутся по модулю $2n+1$. Покажем, что такой гамильтонов контур задает нумерацию вершин, при которой $T=C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$. В силу транзитивности $C$  достаточно доказать
\begin{equation}\label{rrr}\begin{split}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  N^+(v_0) &= \{v_{j}\,|\,1\le j\le n\} \\
  N^-(v_0) &= \{v_{j}\,|\,n+1\le j\le 2n\}.
\end{split}\end{equation}

Для дуги $v_0v_{1}$ множество индексов $\{2,\ldots,2n\}$ разобьем  на  множества
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  S_1 &=& \{j\,|\, v_j\in N^+(v_0)\cap N^-(v_1)\}, \\
  S_0 &=& \{j\,|\, v_j\in N^-(v_0)\cap N^+(v_1)\}, \\
  S_+ &=& \{j\,|\, v_j\in N^+(v_0)\cap N^+(v_1)\}, \\
  S_- &=& \{j\,|\, v_j\in N^-(v_0)\cap N^-(v_1)\}.
\end{eqnarray*}
Поскольку $f_a(T,v_iv_{i+1})=1$, то из Предложения \ref{modu} имеем
\begin{equation}\label{rr1}
|S_1|=0,\ |S_0|=1,\ |S_+|=|S_-|=n-1.
\end{equation}
Заметим, что
\begin{equation}\label{rr2}
\text{если}\ i\in S_+,\ \text{то}\ (i+1)\not\in S_-.
\end{equation}
Иначе $f_a(T,v_iv_{i+1})>1$ (Рис. \ref{ill1}).

	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]%

% точки
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{i+1}$}] (vi5) at (1,4) {};
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{i}$}] (vi4) at (-1,4) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_0$}] (vi) at (1,0) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_1$}] (vi1) at (-1,0) {};

\node[fill,circle,inner sep=1.2pt,label=right:{$v_{2n-1}$}] (vi6) at (3.3,2.5) {};
\node[fill,circle,inner sep=1.2pt,label=right:{$v_{2n}$}] (vi7) at (2.5,1) {};
\node[fill,circle,inner sep=1.2pt,label=left:{$v_3$}] (vi3) at (-3.3,2.5) {};
\node[fill,circle,inner sep=1.2pt,label=left:{$v_2$}] (vi2) at (-2.5,1) {};

%\coordinate [label=above:\textcolor{black}{$\ddots$}] (B) at (2,3);
%\coordinate [label=above:\textcolor{black}{$\ddots$}] (B) at (2,3);
\node[rotate=45] at (-2,3.3) {$\cdots$};
\node[rotate=-45] at (2,3.3) {$\cdots$};
% ребра синие
\draw[-latex,thick](vi6)node {$$} to (vi7);
\draw[-latex,thick](vi7)node {$$} to (vi);
\draw[-latex,thick](vi)node {$$} to (vi1);
\draw[-latex,thick](vi1)node {$$} to (vi2);
\draw[-latex,thick](vi2)node {$$} to (vi3);
\draw[-latex,thick](vi4)node {$$} to (vi5);

% красные стрелки
%\draw[->,red] (vi2) .. controls (0.4,1.2) .. (vi);
\draw[-latex,red,thick](vi)node
        {$$} to (vi4);
\draw[-latex,red,thick](vi1)node
        {$$} to (vi4);

\draw[-latex,red,thick](vi5)node
        {$$} to (vi);
\draw[-latex,red,thick](vi5)node
        {$$} to (vi1);

%\coordinate [label=above:\textcolor{black}{$A$}] (B) at (1,-0.6);
%\coordinate [label=above:\textcolor{black}{$B$}] (B) at (4,-0.6);
%\coordinate [label=above:\textcolor{black}{$C$}] (B) at (7,-0.6);
%\coordinate [label=above:\textcolor{black}{$D$}] (B) at (10,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Если $i\in S_+$ и $(i+1)\in S_-$, то $f_a(T,v_iv_{i+1})>1$.}\label{ill1}
		\end{center}
	\end{figure}




Поскольку $v_2\in N^+(v_1)$, то $2\in S_0\cup S_+$. Если $2\in S_0$, то дуга $v_1v_2$ принадлежит 3-контуру $v_0,v_1,v_2$. Следовательно, $v_3\in N^+(v_1)$ и $3\in  S_+$, что противоречит (\ref{rr1}) и (\ref{rr2}).  Таким образом, $2\in  S_+$. Из (\ref{rr1}) и (\ref{rr2}) имеем
\begin{eqnarray*}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
  S_0 &=& \{n+1\}, \\
  S_+ &=& \{2,\,3,\,\ldots,\,n\}, \\
  S_- &=& \{n+2,\,n+3,\,\ldots,\,2n\}.
\end{eqnarray*}
Отсюда непосредственно следует (\ref{rrr}).
\end{proof}


\begin{theorem}\label{theor2} Пусть в турнире $T\in O(K_{2n+1})$  для каждой дуги $e$ некоторого гамильтонова контура значение $f_a(T,e)$ равно $n$. Тогда выполняется $T\simeq C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$.
\end{theorem}
\begin{proof}
Рассмотрим гамильтонов контур $C=v_0,v_1,\ldots,v_{2n}$ такой, что $$f_a(T,v_iv_{i+1})=n,\ \ 0\le i\le 2n.$$
Из (\ref{okr})
$$|N^-(v_i)\cap N^+(v_{i+1})|=n.$$
Тогда множество $N^-(v_i)$ равно множеству $N^+(v_{i+1})$. Обозначим его через $V_1$. Очевидно, что $v_{i+2}\in V_1$.
Аналогично, поскольку $|N^-(v_{i+1})\cap N^+(v_{i+2})|=n,$ то
$N^-(v_{i+1})=N^+(v_{i+2})=V_2,$ и $v_{i}\in V_2$. Получили разбиение
$V(T)=V_1\cup V_2\cup \{v_{i+1}\}$ (Рис. \ref{ill2}).

	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]

% множества V1 и V2
\draw[blue] (-1.3,2) ellipse (2 and 0.6) node[above=1pt] {$V_1$};
\draw[blue] (2.8,0) ellipse (2 and 0.6) node[below=1pt] {$V_2$};

% точки
\node[fill,circle,inner sep=1.2pt,label=left:{$v_{i+2}$}] (vi2) at (-2.2,2) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i+1}$}] (vi1) at (-1,0) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_i$}] (vi) at (1.6,0) {};

% ребра синие
\draw[-latex,thick](vi1)node
        {$$} to[out=119,in=-61] (vi2);
%\draw[->,blue] (vi1) -- (vi2);
\draw[-latex,thick](vi)node
        {$$} to[out=180,in=0] (vi1);
%\draw[->,blue] (vi) -- (vi1);
%\draw[->,blue] (vi2) -- (vi);
\draw[-latex,thick](vi2)node
        {$$} to[out=-30,in=150] (vi);

% красные стрелки
%\draw[->,red] (vi2) .. controls (0.4,1.2) .. (vi);
\draw[-latex,red,thick](vi2)node
        {$$} to[out=-20,in=140] (3.5,0.1);
\draw[-latex,red,thick](vi)node
        {$$} to[out=-10,in=170] (3.5,0.1);

\draw[-latex,red,thick](0,1.95)node
        {$$} to[out=170,in=10] (vi2);
\draw[-latex,red,thick](0,1.9)node
        {$$} to[out=-60,in=100] (vi);


\end{tikzpicture}

			\caption{Через дугу $v_{i+2}v_{i}$ проходит ровно один контур.}\label{ill2}
		\end{center}
	\end{figure}



В силу эйлеровости турнира
$$N^-(v_{i+2})=V(T)\setminus (V_2\cup \{v_{i+2}\})=(V_1\cup\{v_{i+1}\})\setminus \{v_{i+2}\}.$$
Аналогично
$$N^+(v_{i})=V(T)\setminus (V_1\cup \{v_{i}\})=(V_2\cup\{v_{i+1}\})\setminus \{v_{i}\}.$$
Следовательно, через дугу $v_{i+2}v_{i}$ проходит ровно один контур (Рис. \ref{ill2}).

 Таким образом, для каждой дуги $e$  гамильтонова контура $$v_0,v_{-2},v_{-4},\ldots,v_2$$ значение $f_a(T,e)$ равно 1. По Теореме \ref{theor1} выполняется $$T\simeq G_{2n+1}(1,\ldots,n;+1,\ldots,+1).$$

\end{proof}

\section{Эйлеровы ориентации полного графа с удаленным гамильтоновым циклом}

Рассмотрим  гамильтонов контур $C=v_0,v_1,\ldots,v_{2n}$ в эйлеровом турнире $T\in O(K_{2n+1})$. Для каждой вершины $v_i$ рассмотрим систему треугольников $U_i=(q_1^i,\ldots,q_{2n-1}^i)$, где $q_s^i=v_i,v_{i+s},v_{i+s+1}$.
Таким образом, множестве $U_0\cup\cdots \cup U_{2n+1}$ является множеством всех треугольников в $T$, имеющих общее с $C$ ребро.

 По построению справедливы следующие два предложения (Рис. \ref{ill3}).

	\begin{figure}
		\begin{center}
\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]



% точки
\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i}$}] (vi) at (0,0) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i+1}$}] (vi1) at (-2,0.5) {};
\node[fill,circle,inner sep=1.2pt,label=left:{$v_{i+2}$}] (vi2) at (-3.3,2) {};
\node[fill,circle,inner sep=1.2pt,label=left:{$v_{i+3}$}] (vi3) at (-3.5,3.5) {};
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{s-1}$}] (vi4) at (-3,5.3) {};
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{s}$}] (vi5) at (-1,6) {};
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{s+1}$}] (vi6) at (1,6) {};
\node[fill,circle,inner sep=1.2pt,label=above:{$v_{s+2}$}] (vi7) at (3,5.3) {};
\node[fill,circle,inner sep=1.2pt,label=right:{$v_{i-2}$}] (vi8) at (3.3,2.8) {};
\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i-1}$}] (vi9) at (2,0.5) {};

%\coordinate [label=above:\textcolor{black}{$\ddots$}] (B) at (2,3);
%\coordinate [label=above:\textcolor{black}{$\ddots$}] (B) at (2,3);
\node[rotate=70] at (-2.6,3.4) {$\cdots$};
\node[rotate=-70] at (2.3,2.9) {$\cdots$};
% ребра синие
\draw[-latex,red,thick](vi6)node {$$} to (vi7);
\draw[-latex,red,thick](vi5)node {$$} to (vi6);
\draw[-latex,red,thick](vi)node {$$} to (vi1);
\draw[-latex,red,thick](vi1)node {$$} to (vi2);
\draw[-latex,red,thick](vi2)node {$$} to (vi3);
\draw[-latex,red,thick](vi4)node {$$} to (vi5);
\draw[-latex,red,thick](vi8)node {$$} to (vi9);
\draw[-latex,red,thick](vi9)node {$$} to (vi);


\draw[-latex,thick](vi2)node {$$} to (vi);
\draw[-latex,thick](vi3)node {$$} to (vi);
\draw[-latex,thick](vi)node {$$} to (vi4);
\draw[-latex,thick](vi)node {$$} to (vi5);
\draw[-latex,thick](vi6)node {$$} to (vi);
\draw[-latex,thick](vi7)node {$$} to (vi);
\draw[-latex,thick](vi8)node {$$} to (vi);

\node at (-1.9,0.83) {$q^i_1$};
\node at (-2.5,1.95) {$q^i_2$};
\node at (-1.4,4) {$q^i_{s-1}$};
\node at (0,4.5) {$q^i_{s}$};
\node at (1.4,4) {$q^i_{s+1}$};
\node at (1.58,0.77) {$q^i_{2n-1}$};


% красные стрелки
%\draw[->,red] (vi2) .. controls (0.4,1.2) .. (vi);
%\draw[-latex,red,thick](vi)node         {$$} to (vi4);
%\draw[-latex,red,thick](vi1)node        {$$} to (vi4);

%\draw[-latex,red,thick](vi5)node        {$$} to (vi);
%\draw[-latex,red,thick](vi5)node        {$$} to (vi1);

%\coordinate [label=above:\textcolor{black}{$A$}] (B) at (1,-0.6);
%\coordinate [label=above:\textcolor{black}{$B$}] (B) at (4,-0.6);
%\coordinate [label=above:\textcolor{black}{$C$}] (B) at (7,-0.6);
%\coordinate [label=above:\textcolor{black}{$D$}] (B) at (10,-0.6);

\end{tikzpicture}%\hspace{1cm}
			\caption{Система треугольников $U_i$. Треугольники $q_1^i$ и $q_s^i$ являются контурами}\label{ill3}
		\end{center}
	\end{figure}






\begin{proposition}\label{peres}
\begin{equation*}
  U_i\cap U_j=\left\{
     \begin{array}{ll}
       \varnothing, & \hbox{если } \min (|i-j|,2n+1-|i-j|)\ne 2 ;\\
       v_i,v_{i+1},v_{i+2}, & \hbox{если} \ j=i+2.
     \end{array}
   \right.
\end{equation*}
\end{proposition}

\begin{proposition} \label{chered}
Если в $U_i$ треугольник $q_s^i$ является контуром,  $s\le 2n-2,$ то $q_{s+1}^i$ не является контуром.
\end{proposition}

Обозначим через $f_a(T,C)$ количество 3-контуров в множестве $U_0\cup\cdots \cup U_{2n+1}$.
Таким образом, это количество 3-контуров в турнире $T$, имеющих хотя бы одну общую дугу с гамильтоновым контуром $C$.



\begin{proposition}\label{ner}
$$2n+1\le f_a(T,C)\le (n-1)(2n+1).$$
\end{proposition}
\begin{proof}
Заметим, что треугольник $q_s^i$ является контуром тогда и только тогда, когда $v_{i+s}\in N^+(v_i)$ и $v_{i+s+1}\in N^-(v_i)$. Поскольку $v_{i+1}\in N^+(v_i)$ и $v_{i-1}\in N^-(v_i)$, то по крайней мере один контур в $U_i$ есть (Рис. \ref{ill3}). Причем если $q_1^i$ --- контур, то будет по крайней мере еще один переход от исходящей из $v_i$ дуги к входящей, а, следовательно, еще один контур.
 Аналогично, если $q_{2n-1}^i$ является контуром, то контуров не менее двух. Следовательно, по Предложению \ref{peres} имеем $f_a(T,C)\ge 2n+1.$

По Предложению \ref{chered} если в $U_i$ больше $(n-1)$ контуров, то их $n$ штук, и среди них есть $q_1^i$ и $q_{2n-1}^i$, которые по Предложению \ref{peres} также входят в $U_{i+2}$ и $U_{i-2}$ соответственно. Следовательно, $f_a(T,C)\le (n-1)(2n+1).$
\end{proof}


\begin{theorem}  Для любой ориентации $D\in O(K_{2n+1}\setminus C)$  число 3-контуров в ней удовлетворяет неравенствам
$$(2n+1)\left(\frac{(n+1)n}{6}-(n-1)\right)\le f_a(D)\le (2n+1)\left(\frac{(n+1)n}{6}-1\right).$$
\end{theorem}
\begin{proof}
Любая ориентация $D\in O(K_{2n+1}\setminus C)$ получается из некоторого эйлерова турнира $T\in O(K_{2n+1})$ удалением  гамильтонова контура $C=v_0,v_1,\ldots,v_{2n}$.  В силу (\ref{tra}) имеем
\begin{equation}\label{tra1}
  f_a(D)=f_a(T)-f_a(T,C)=\frac{2n+1}{3}\binom{n+1}{2}-f_a(T,C).
\end{equation}
Следовательно, искомые неравенства следуют из Предложения \ref{ner}.
\end{proof}

\begin{theorem}  Существует и единственная с точностью до разворота всех дуг ориентация $D\in O(K_{2n+1}\setminus C)$, для которой справедливо равенство
\begin{equation}\label{yy1}
  f_a(D)=(2n+1)\left(\frac{(n+1)n}{6}-(n-1)\right).
\end{equation}
\end{theorem}
\begin{proof}
Пусть для $D\in O(K_{2n+1}\setminus C)$ верно (\ref{yy1}). Тогда его можно дополнить гамильтоновым контуром $C=v_0,v_1,\ldots,v_{2n}$ до турнира $T$. По Предложению \ref{ner} для $C$ верно
\begin{equation}\label{rav1}
f_a(T,C)=(n-1)(2n+1).
\end{equation}
Как было показано в доказательстве Предложения \ref{ner}, каждая система треугольников $U_i$ в сумму (\ref{rav1}) числа всех 3-контуров, имеющих общую дугу с $C$, вносит вклад не больше $(n-1)$. А следовательно, для достижения равенства должна вносить ровно $(n-1)$. Это возможно  в двух случаях: когда в  $U_i$ контурами являются $n$ треугольников $q_1^i$, $q_3^i$, $q_5^i,\ldots,$ $q_{2n-1}^i$, либо когда в $U_i$ контурами являются $(n-1)$ треугольник $q_2^i$, $q_4^i$, $q_6^i,\ldots,$ $q_{2n}^i$.

Из Предложения \ref{peres}  следует, что
если для некоторой вершины $v_i$ система треугольников $U_i$ содержит $n$ контуров, то  и система $U_{i+2}$ тоже содержит $n$ контуров. Поскольку вершин в графе нечетное число, то тогда для любой вершины $v_i$ система треугольников $U_i$ содержит $n$ контуров. Таким образом, для нумерации вершин, заданной гамильтоновым контуром $C$, имеем
\begin{equation}\label{tur}
D=C_{2n+1}(2,\ldots,n;-1,+1,-1,+1,\ldots).
\end{equation}
 Причем по Предложению \ref{Li} и Теореме \ref{theor2} эта ориентация эквивалентна ориентации $C_{2n+1}(1,\ldots,n-1;+1,\ldots,+1)$, которая получается из турнира $C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$ удалением дуг, соединяющих вершины на расстоянии  $n$.

Остается случай, когда для любой вершины $v_i$ система $U_i$ содержит $(n-1)$ контур. Это полностью определяет ориентацию $D$, которая равна $C_{2n+1}(2,\ldots,n;+1,-1,+1,-1,\ldots)$ и получается из (\ref{tur}) разворотом всех дуг.
\end{proof}

\begin{theorem}  Существует и единственная с точностью до разворота всех дуг ориентация $D\in O(K_{2n+1}\setminus C)$, что
\begin{equation}\label{yy2}
  f_a(D)=(2n+1)\left(\frac{(n+1)n}{6}-1\right).
\end{equation}
\end{theorem}
\begin{proof}
Пусть для $D\in O(K_{2n+1}\setminus C)$ верно (\ref{yy2}). Тогда $D$ можно дополнить гамильтоновым контуром $C=v_0,v_1,\ldots,v_{2n}$ до турнира $T$. По Предложению \ref{ner} для $C$ верно
\begin{equation*}
f_a(T,C)=(2n+1).
\end{equation*}
Из Предложений \ref{chered} и \ref{peres} для любой вершины $v_i$ система треугольников $U_i$ содержит один или два контура, причем, если один, то это $q_n^i$, а если два, то $q_1^i$ и $q_{2n-1}^i$. Следовательно, если для всех $i$ система $U_i$ содержит один контур, то любая дуга $e$ гамильтонова контура $C$ удовлетворяет равенству $f_a(T,e)=1$, и по Теореме \ref{theor1} и Предложению \ref{Li}
\begin{equation}\label{tur1}
D=C_{2n+1}(2,\ldots,n;+1,\ldots,+1).
\end{equation}
и получается из турнира $C_{2n+1}(1,\ldots,n;+1,\ldots,+1)$ удалением дуг, соединяющих вершины на расстоянии  $1$.

Если же найдется такое $i$, что система $U_i$ содержит два контура, то $U_{i+2}$ тоже содержит два контура, а следовательно, в силу нечетности числа вершин, все $U_j$ содержат два контура. Это полностью определяет ориентацию $D$, которая равна $C_{2n+1}(2,\ldots,n;-1,\ldots,-1)$ и получается из (\ref{tur1}) разворотом всех дуг.
\end{proof}


\section{Эйлеровы ориентации полного графа с удаленным паросочетанием}
Вершину $v$ в $H \in O(K_{2n} \setminus M)$ назовём противоположной для $u$, если $v$ и $u$ не смежны в $H$. Таким образом все вершины в $H$ разбиваются на пары противоположных вершин.
Будем считать, что все вершины пронумерованы от $0$ до $2n-1$, $v_i$ и $v_{i+n}$ --- противоположные вершины для всех $i \in \{0,\dots,n-1\}$.
%
%\begin{proposition}\label{sub} Для любого $\lambda \in \{A, B, C, D\}$ и $H \in O(K_{2n} \setminus M)$ верны неравенства
%	$$0 \leq \tilde{f}_{\lambda}(H) \leq {n \choose 2}.$$
%\end{proposition}


\begin{theorem}
	\label{th3}
	Для ориентации $H \in  O(K_{2n} \setminus M)$ следующие оценки справедливы и достижимы:
	\begin{align*}
		2 {n \choose 3} \leq &  f_a(H) \leq 2 {n+1 \choose 3}, \text{ если $n$ --- нечетно;}\\
		2 {n \choose 3} \leq & f_a(H) \leq \frac{(n-2)n(n+2)}{3}, \text{ если $n$ --- четно.}
	\end{align*}
\end{theorem}

Для доказательства Теоремы \ref{th3} потребуется ряд вспомогательных утверждений.
Обозначим через $r_i$ количество дуг, ведущих из $N^+(v_i)$ в $N^-(v_i)$.
Тогда очевидно, что
\begin{equation}\label{edm1}
	f_a(H) = \frac{1}{3}\sum_{i=0}^{2n-1} r_i.
\end{equation}
Количество дуг внутри множества $N^+(v_i)$ обозначим через $s_i$, а количество дуг из $N^+(v_i)$ в $v_{i+n}$ --- через $w_i$.
Нетрудно видеть, что
\begin{equation}\label{edm2}
	r_i + s_i + w_i = (n-1)^2.
\end{equation}


\begin{lemma}
	\label{lem1}
	Для любой ориентации $H \in  O(K_{2n} \setminus M)$ выполнено
	\begin{equation*}
		f_a(H) \geq 2 {n \choose 3}.
	\end{equation*}
\end{lemma}
\begin{proof}
	Заметим, что $s_i \leq {n-1 \choose 2}$ и $w_i \leq n-1$.
	Тогда из (\ref{edm2}) следует
	\begin{equation*}
		r_i \geq (n-1)^2 - (n-1) - {n-1 \choose 2} = \frac{(n-1)(n-2)}{2}.
	\end{equation*}
	Отсюда, используя (\ref{edm1}) получаем
	
	\begin{equation*}
		f_a(H) = \frac{1}{3}\sum_{i=0}^{2n-1} r_i \geq \frac{1}{3} \cdot 2n \cdot \frac{(n-1)(n-2)}{2} = 2 {n \choose 3}.
	\end{equation*}
\end{proof}


\begin{lemma}
	\label{lem2}
	Для любой ориентации $H \in  O(K_{2n} \setminus M)$ выполнено
	\begin{equation*}
		f_a(H) \leq 2{n+1 \choose 3}.
	\end{equation*}
\end{lemma}
\begin{proof}
	Заметим, что $s_i \geq {n-1 \choose 2} - \frac{n-1}{2}$ и $w_i \geq 0$.
	Тогда из (\ref{edm2}) следует
	\begin{equation*}
		r_i \leq (n-1)^2 - \left({n-1 \choose 2} - \frac{n-1}{2}\right) = \frac{(n-1)(n+1)}{2}.
	\end{equation*}
	Отсюда, используя (\ref{edm1}) получаем
	
	\begin{equation*}
		f_a(H) = \frac{1}{3}\sum_{i=0}^{2n-1} r_i \geq \frac{1}{3} \cdot 2n \cdot  \frac{(n-1)(n+1)}{2} = 2 {n+1 \choose 3}.
	\end{equation*}
\end{proof}


Заметим, что при четном $n$ каждое из множеств $N^+(v_i)$ и $N^-(v_i)$ содержит нечетное число вершин.
Отсюда следует
\begin{proposition}\label{odd}
	Для любого чётного $n$ для любой ориентации $H \in  O(K_{2n} \setminus M)$ для фиксированного $i$ существует хотя бы одна пара противоположных вершин $v_j$ и $v_{j+n}$ таких, что одна из них принадлежит $N^+(v_i)$, а вторая $N^-(v_i)$.
\end{proposition}

\begin{lemma}
	\label{lem3}
	Для любого чётного $n$ для любой ориентации $H \in  O(K_{2n} \setminus M)$ выполнено
	\begin{equation*}
		f_a(H) \leq \frac{(n-2)n(n+2)}{3}.
	\end{equation*}
\end{lemma}
\begin{proof}
	Поскольку при четном $n$ число $\frac{n-1}{2}$ не целое, то нижнюю оценку для $s_i$ из доказательства Леммы \ref{lem2} можно усилить следующим образом:
	\begin{equation*}
		s_i \geq {n-1 \choose 2} - \frac{n-2}{2}.
	\end{equation*}
	Таким образом, используя (\ref{edm2}), получаем верхнюю оценку:
\begin{eqnarray}
% используйте \nonumber для того, чтобы убрать номер (вставляется перед каждым уравнением)
	 f_a(H) &\leq & \frac{1}{3}\sum_{i=0}^{2n-1} r_i = \frac{1}{3} \left( (n-1)^2 - s_i - w_i \right) \leq \nonumber \\
   &\leq & \frac{1}{3} \sum_{i=0}^{2n-1} \left( (n-1)^2 - \left(  {n-1 \choose 2} - \frac{n-2}{2} \right) - w_i \right) \nonumber \\
   &=& \frac{1}{3} \left( 2n \cdot \frac{n^2 - 2}{2} - \sum_{i=0}^{2n-1} w_i\right). \label{edm3}
\end{eqnarray}
	
	Докажем, что $\sum\limits_{i=0}^{2n-1} w_i \geq 2n$.
	\bigskip

	
	Заметим, что
	\begin{align*}
		n - 1 &= |N^+(v_i)| = |(N^+(v_i) \cap N^+(v_{i+n}))| + w_i = \\
		&= |N^+(v_{i+n})| = |(N^+(v_i) \cap N^+(v_{i+n}))| + w_{i+n}.
	\end{align*}
	Поэтому для пары противоположных вершин $v_i$ и $v_{i+n}$ справедливо
	\begin{equation} \label{lem30}
		w_i = w_{i+n}
	\end{equation}
	
	Пусть $\mathcal{I}_0 =\{i \in \{0, \dots, n-1\}\ |\ w_i = 0\}$, а $\mathcal{I}^\prime_0 =\{i + n\ |\ i \in \mathcal{I}_0\}$.
	Таким образом, для любого $j \notin \mathcal{I}_0 \cup \mathcal{I}^\prime_0$ имеем
	\begin{equation} \label{lem31}
	w_j \geq 1.
	\end{equation}
	По Предложению \ref{odd} для каждого $i \in \mathcal{I}_0$ будет существовать $j$ такое, что
	\begin{equation} \label{lem32}
		v_j \in N^+(v_i) \cap N^+(v_{i+n}),\ \  v_{j+n} \in N^-(v_i) \cap N^-(v_{i+n}).
	\end{equation}
	
	Рассмотрим отображение $\varphi$, которое любому $i \in \mathcal{I}_0$ ставит в соответствие некоторое $j$, удовлетворяющее (\ref{lem32}) (Рис. \ref{ill4}).
	\begin{figure}
		\begin{center}
			\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]
				
				% множества V1 и V2
				\draw[blue] (-2,2) ellipse (1.5 and 0.6) node[above=1pt] {};
				\draw[blue] (2,2) ellipse (1.5 and 0.6) node[below=1pt] {};
				
				
				% точки
				\node[fill,circle,inner sep=1.2pt,label=left:{$v_{i}$}] (vi) at (0,4) {};
				\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i+n}$}] (vin) at (0,0) {};
				\node[fill,circle,inner sep=1.2pt,label=below:{$v_{j}$}] (vj) at (-1.5,2) {};
				\node[fill,circle,inner sep=1.2pt,label=below:{$v_{j+n}$}] (vjn) at (1.5,2) {};
				
				\draw[-latex,thick](vi)node
				{$$} to (-3,2.43);
				\draw[-latex,thick](vi)node
				{$$} to (-2,2.53);
				\draw[-latex,thick](vi)node
				{$$} to (-1,2.33);
				
				\draw[-latex,thick](vin)node
				{$$} to (-3,1.57);
				\draw[-latex,thick](vin)node
				{$$} to (-2,1.47);
				\draw[-latex,thick](vin)node
				{$$} to (-1,1.67);
				
				\draw[-latex,thick](3,2.49)
				to (vi)node {$$};
				\draw[-latex,thick](2,2.59)
				to (vi)node {$$};
				\draw[-latex,thick](1,2.43)
				to (vi)node {$$} ;
				
				\draw[-latex,thick](3,1.51)
				to (vin)node {$$};
				\draw[-latex,thick](2,1.41)
				to (vin)node {$$} ;
				\draw[-latex,thick](1,1.57)
				to (vin)node {$$};
				
				\draw[dashed, thin](vi)node {$$} -- (vin)node{$$};
				\draw[dashed, thin](vj)node {$$} -- (vjn)node{$$};
				
			\end{tikzpicture}
			
			\caption{$w_i = 0$, $\varphi(i) = j$}\label{ill4}
		\end{center}
	\end{figure}
	Обозначим $\mathcal{M} = \varphi(\mathcal{I}_0)$, а $\mathcal{M}^\prime =\{i + n\ |\ i \in \mathcal{M}\}$.
	Нетрудно видеть, что
	\begin{equation} \label{lem33}
	 |\mathcal{M}| = |\mathcal{M}^\prime| \leq |\mathcal{I}_0|.
	\end{equation}
	Пусть теперь $\mathcal{R} = \{0, \dots, 2n-1\} \setminus (\mathcal{M} \cup \mathcal{M}^\prime \cup \mathcal{I}_0 \cup \mathcal{I}_0^\prime)$.
	Из (\ref{lem31}) получаем  неравенство
	\begin{equation} \label{lem34}
		\sum_{i \in \mathcal{R}} w_i \geq  |\mathcal{R}|.
	\end{equation}
	
	Имеем разбиение $\{0, \dots, 2n-1\} = \mathcal{I}_0 \sqcup \mathcal{I}^\prime_0 \sqcup \mathcal{M} \sqcup \mathcal{M}^\prime \sqcup \mathcal{R}$.
	Из (\ref{lem33}) получаем, что
	\begin{equation} \label{lem35}
		|\mathcal{R}| \geq 2n - 4 |\mathcal{I}_0|.
	\end{equation}
	

	

	
	Пусть $j \in \mathcal{M}$.
	Тогда для любого $i \in \varphi^{-1}(j)$ получаем $v_i, v_{i+n} \in N^-(v_j) \cap N^+(v_{j+n})$ (Рис.  \ref{ill5}).
	\begin{figure}
		\begin{center}
			\begin{tikzpicture}[thick,scale=0.99,shorten >=2pt]
				
				% множества V1 и V2
				\draw[blue] (-2,2) ellipse (1.5 and 0.6) node[above=1pt] {};
				\draw[blue] (2,2) ellipse (1.5 and 0.6) node[above=1pt] {};
				
				% точки
				\node[fill,circle,inner sep=1.2pt,label=left:{$v_{j}$}] (vj) at (0,4) {};
				\node[fill,circle,inner sep=1.2pt,label=below:{$v_{j+n}$}] (vjn) at (0,0) {};
				\node[fill,circle,inner sep=1.2pt,label=left:{$v_{i}$}] (vi) at (-2.5,2) {};
				\node[fill,circle,inner sep=1.2pt,label=below:{$v_{i+n}$}] (vin) at (-1.5,2) {};
				
				\draw[-latex,thick](vj)node {$$} to (vi)node {$$};
				\draw[-latex,thick](vj)node {$$} to (vin)node {$$};
				\draw[-latex,thick](vi)node {$$} to (vjn)node {$$};
				\draw[-latex,thick](vin)node {$$} to (vjn)node {$$};
				\draw[dashed, thin](vj)node {$$} -- (vjn)node{$$};
				
			\end{tikzpicture}
			
			\caption{$i \in \varphi^{-1}(j)$}\label{ill5}
		\end{center}
	\end{figure}
	Следовательно $w_j \geq 2|\varphi^{-1}(j)|$.
	Значит,
	\begin{equation} \label{lem36}
		\sum_{j \in \mathcal{M}} w_j \geq 2|\mathcal{I}_0|.
	\end{equation}
	В результате, в силу $(\ref{lem30}), (\ref{lem34}), (\ref{lem35}), (\ref{lem36})$, имеем:
	\begin{equation*}
	\sum_{i=0}^{2n-1} w_i = \sum_{i \in \mathcal{M}} w_i + \sum_{i \in \mathcal{M}^\prime} w_i + \sum_{i \in \mathcal{R}} w_i = 2 \sum_{i \in \mathcal{M}} w_i + \sum_{i \in \mathcal{R}} w_i \geq 4|\mathcal{I}_0| + |\mathcal{R}| \geq 2n.
	\end{equation*}

	Подставляя полученную оценку  в (\ref{edm3}), получаем
	\begin{equation*}
		f_a(H) \leq \frac{1}{3} \left( 2n \cdot \frac{n^2 - 2}{2} - \sum_{i=0}^{2n-1} w_i\right) \leq \frac{(n-2)n(n+2)}{3}.
	\end{equation*}
\end{proof}

Для эйлеровых ориентаций вида $C_{2n}(d_1,\ldots,d_{n-1};t_1,\ldots,t_{n-1})$ введём обозначение
$$
\Delta(C_{2n}(d_1,\ldots,d_{n-1};t_1,\ldots,t_{n-1})) = \left|\left\{(i, j) |\ i < j,\ d_i + d_j = n, \ t_i \neq t_j\right\}\right|.
$$

\begin{proposition}\label{Delta}
	$$0 \leq \Delta(C_{2n}(1,\dots,n-1;t_1,\ldots,t_{n-1})) \leq \left\lfloor\frac{n-1}{2}\right\rfloor$$ и существуют наборы $t_1, \dots, t_{n-1}$, на которых достигаются нижняя и верхняя оценки.
\end{proposition}

Нетрудно видеть, что нижняя оценка достигается на любом наборе, в котором все $t_i$ принимают одно и то же значение.
Верхняя оценка достигается на любом антисимметричном наборе $t_1, \dots, t_{n-1}$.
Например,
$$
t_1, \dots, t_{n-1} = \underbrace{-1, \dots, -1}_{\frac{n-1}{2}}, \underbrace{+1, \dots, +1}_{\frac{n-1}{2}}
$$
для нечётного $n$, и
$$
t_1, \dots, t_{n-1} = \underbrace{-1, \dots, -1}_{\frac{n-2}{2}}, -1, \underbrace{+1, \dots, +1}_{\frac{n-2}{2}}
$$
для чётного.

\bigskip

\begin{lemma}
	\label{lem4}
	Пусть $T = C_{2n}(1,\dots,n-1;t_1,\ldots,t_{n-1})$.
	Тогда
	\begin{equation*}
		f_a(T) =
		\begin{cases}
			2{n+1 \choose 3} - 2n(\frac{n-1}{2} - \Delta(T)), \text{ $n$ --- нечетно;} \\
			2{n+1 \choose 3} - (2n(\frac{n-2}{2} - \Delta(T)) + n), \text{ $n$ --- четно.}
		\end{cases}
	\end{equation*}
\end{lemma}
\begin{proof}
	Для каждого $i \in \{0, \dots, n-1\}$ добавим в ориентацию $T$ дугу из $v_i$ в $v_{i+n}$.
	Получим турнир $T^\prime$, для которого
	\begin{equation*}
		\deg_+ v_i = \begin{cases}
			n, i \in \{0, \dots, n-1\}; \\
			n-1, i \in \{n, \dots, 2n-1\}.
		\end{cases}
	\end{equation*}
	По \cite{Per} имеем:
	\begin{equation*}
		f_a(T^\prime) = {2n \choose 3} - \sum_{i=0}^{2n-1} {\deg_+ v_i \choose 2} = {2n \choose 3} - n {n \choose 3} - n {n-1 \choose 3} = 2 {n+1 \choose 3}.
	\end{equation*}
	
	Каждая добавленная дуга может образовать в $T^\prime$ 3-контур только с парой дуг, соединияющих вершины на расстояниях равных $j$ и $n-j$ для некоторого $j \in \{1, \dots, n-1\}$.
	Если $t_j \neq t_{n-j}$, то добавленная дуга $(v_i, v_{i+n})$ не образует 3-контур с дугами длин $j$ и $n-j$.
	Иначе, добавленная дуга образует ровно 2 3-контура с дугами этих длин (кроме случая когда для четного $n$ и $j = n/2$ будет получаться один 3-контур).
	
	Таким образом, для нечетного $n$ каждая добавленная дуга образует $2(\frac{n-1}{2} - \Delta(T))$ 3-контуров.
	Для четного $n$ --- образует $(1 + 2(\frac{n-1}{2} - \Delta(T)))$ 3-контуров.
\end{proof}

Из Лемм \ref{lem1}, \ref{lem2}, \ref{lem3}, \ref{lem4} и Предложения \ref{Delta} напрямую следует доказательство теоремы \ref{th3}.



\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{Per}
Perezhogin A.~L., Bykov I.~S., Avgustinovich S.~V.,
\href{http://doi.org/10.33048/semi.2024.21.028}{Small length circuits in Eulerian orientations of graphs}, Siber. Electr. Math. Reports. 14 (2024) , 370-382.

\bibitem{Kir1}
Kireeva T.~E.,
\href{http://doi.org/10.17377/semi.2018.15.111}{\it Perfect orientation colorings of cubic graphs}, Siber. Electr. Math. Reports. 15 (2018) , 1353-1360. %[Russian, English abstract]

\bibitem{Tar}
Taranenko A.~A., \href{http://doi.org/10.1016/j.laa.2020.08.012}{\it
	Algebraic properties of perfect structures}.
Linear Algebra Appl. 607 (2020), 286-306.

\bibitem{PCh}
Пяткин А.~В., Черных О.~И., \href{https://doi.org/10.33048/daio.2022.29.723}{\it О максимальном числе открытых треугольников в графах с одинаковым числом вершин и рёбер.
} Дискретный анализ и исследование операций, 29, 1, 46-55 (2022)

\bibitem{PLy}
Pyatkin A.~V., \href{https://doi.org/10.33048/daio.2024.31.793}{\it On the maximum number of open triangles in graphs with few edges}, J. Appl. Industr. Math., 18:3 (2024), 516–520.


\end{thebibliography}
\end{document}


