\documentclass[a4paper]{amsart}
%\usepackage[cp866]{inputenc}
%\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
%\usepackage{geometry}\geometry{a4paper,top=1.0cm,bottom=1.5cm,left=1.2cm,right=1.2cm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}


\usepackage[cp1251]{inputenc}
\advance\hoffset-27mm \advance\textwidth54mm \advance\voffset-30mm \advance\textheight54mm

\usepackage{graphics}
\usepackage{epsfig}
\usepackage{graphicx}

%\newtheorem{theorem}{Theorem}[section]
\newtheorem*{lemma}{Лемма}

\newcounter{num}
\setcounter{num}0

\newcommand{\z} {\par\refstepcounter{num}
{\noindent{\bf \arabic{num}. }}}
%\newcommand{\zz}{    \refstepcounter{num}
%{\noindent {\bf \arabic{num} }}}
%\newcommand{\zzz}{}

\newcommand{\sol} {\par\refstepcounter{num}
{\noindent{\bf Решение задачи \arabic{num}. }}}

\newcounter{pict}
\setcounter{pict}0

\newcommand{\pic}{\par \refstepcounter{pict}
{\noindent{Рис. \arabic{pict} }}}

%\newcommand{\sl}{\par\refstepcounter{num}
%{\noindent{\bf \arabic{num}. }}}

\def\misha{\marginpar{\bf * Мяу}}

\let\emp\varnothing

\def\cis{$CIS$-\noindent}


\begin{document}
\title {$CIS$-графы}
\date {}
\maketitle


%\large

Напомним основные определения. Пусть дан граф $G$.

{\it Подграфом} графа $G$ на вершинах $v_1,v_2,\dots,v_n$ (где $v_1,v_2,\dots,v_n$~-- часть вершин
графа~$G$) называется граф, вершинами которого являются вершины $v_1,v_2,\dots,v_n$, и между ними
проведены {\bf все} рёбра, которые были проведены в графе $G$.

{\it Дополнением графа $G$} называется граф, вершинами которого являются вершины графа $G$, но две
вершины соединяются ребром в том и только в том случае, если они не были соединены ребром в графе
$G$.

{\it Кликой} в графе $G$ называется любое множество попарно соединённых вершин. Соответственно
{\it независимым множеством} называется любое множество попарно не соединённых вершин. Клика
(независимое множество) называется {\it максимальной} ({\it максимальным}), если она не содержится
ни в какой большей клике (независимом множестве).

Главным определением этой серии задач является определение $CIS$-графа.

{\it $CIS$-графом} называется граф, в котором любая максимальная клика $C$ пересекается с любым
максимальным независимым множеством $S$. Например, цикл длины четыре является $CIS$-графом, а
$\Pi$-граф, изображённый на рисунке~\ref{1}, не является $CIS$-графом.

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.0}\\
\pic\label{1}
\end{tabular}
\end{center}

\smallskip

{\bf А много ли $CIS$-графов? Задачи на определение}.

\smallskip

\z Покажите, что несвязное объединение двух $CIS$-графов $G_1$ и $G_2$ является $CIS$-графом.

\noindent Примечание. Чтобы получить несвязное объединение графов $G_1$ и $G_2$, нужно объединить
их (считая все вершины различными!) и не проводить больше никаких ребер.

\smallskip

\z Найдите все $CIS$-графы, в которых нет трёх попарно соединённых вершин. Проверьте, что вершины
каждого из них можно покрасить в два цвета так, чтобы любые две соседние вершины были разных
цветов.

\smallskip

\z Пусть из $CIS$-графа удалили вершину, из которой выходило одно ребро. Покажите, что получился
снова $CIS$-граф.
\smallskip

\z а) Назовём вершину {\it хорошей}, если любые два её соседа соединены (то есть она вместе с
соседями образует клику). Докажите, что если в графе любая максимальная клика содержит хорошую
вершину, то это $CIS$-граф.

b) Покажите, что обратное неверно.

\smallskip

\z Рассмотрим граф, множество вершин которого является объединением пересекающихся клики и
независимого множества. Покажите, что он является $CIS$-графом.

{\it Подстановкой} графа $G_1$ в граф $G_2$ будем называть следующую операцию: некоторая
фиксированная вершина $A$ графа $G_2$ заменяется на граф $G_1$, между вершинами графа $G_1$ и
графа $G_2$ проводятся в точности те же ребра, которые были между $A$ и остальными вершинами
$G_2$.

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.8}\\
\pic
\end{tabular}
\end{center}
\smallskip

\z Пусть в результате подстановки графа $G_1$ в граф $G_2$ получился $CIS$-граф. Покажите, что и
$G_1$, и $G_2$ были $CIS$-графами.\label{podst}

\smallskip

\z Докажите, что любой граф является подграфом некоторого $CIS$-графа.

\smallskip

\z Рассмотрим два множества графов $G_1,G_2,G_3,\dots$ и $H_1,H_2,H_3,\dots$, причём графов в
множествах поровну, но их число может быть как конечное, так и бесконечное. Теперь рассмотрим
множество всех графов, для которых выполнено условие:
%если среди подграфов данного графа есть граф
%$G_i$, то среди них же есть граф $H_i$, содержащий $G_i$.
если среди подграфов данного графа есть граф $G_i$, то этот $G_i$ дополняется до подграфа $H_i$,
то есть этот $G_i$ содержится в некотором подграфе $H_i$ данного графа.

a) Подберите графы $G_i$ и $H_i$ так, чтобы получилось множество всех $CIS$-графов.

b) Можно ли выбрать конечное число графов $G_i$ и $H_i$ так, чтобы получилось множество всех
$CIS$-графов?

\par\refstepcounter{num}
\noindent{\bf \arabic{num}$^*$.}
%\z %\misha
Пусть в графе существует ровно одна пара из непересекающихся максимальной клики $C$ и
максимального независимого множества $S$.

a) Докажите, что в $G$, кроме вершин из $C\cup S$, не может быть ровно одной вершины.

b) То же для двух вершин.

c) Попробуйте доказать, что тогда множество вершин этого графа совпадает с $C\cup S$.

\bigskip


{\bf Расчёски и гребешки}.
\smallskip

Класс графов называется замкнутым относительно подстановки, если из графов $G_1$ и $G_2$ этого
класса с помощью подстановки получается снова граф этого класса. Класс графов называется точно
замкнутым относительно подстановки, если дополнительно потребовать, чтобы графы этого класса могли
получаться подстановкой только из графов этого класса.

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


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

% Класс графов называется наследственным,
%если для каждого графа из этого класса все его подграфы также лежат в этом классе.

Очевидно, что класс $CIS$-графов замкнут относительно дополнения. В задаче~\ref{podst} мы также
показали, что он замкнут относительно подстановки. Будем исследовать $CIS$-графы дальше.

\smallskip

\z a) Докажите, что если в графе существует пара непересекающихся максимальной клики и
максимального независимого множества, то этот граф содержит в качестве подграфа $\Pi$-граф.

b) Покажите, что обратное неверно.

%\smallskip

%{\bf Определение.} Будем говорить, что в данном графе $G$ первый подграф дополняется (не
%путать с дополнением графа) до второго подграфа графа $G$, если первый подграф является подграфом
%второго подграфа графа $G$.

\smallskip

{\bf Определение.} $k$-расчёской ($k\geqslant 2$) называется граф на $2k$ вершинах, в котором
первые $k$ вершин попарно соединены, другие $k$ вершин попарно не соединены, и ещё проведено $k$
рёбер, соединяющие $i$-ю вершину  первой группы из $k$ вершин с $i$-ой вершиной второй группы для
каждого $i=1,2,\dots,k$. Далее, $k$-гребешком называется граф, полученный прибавлением одной
вершины к $k$-расчёске, причем новая вершина соединена только со всеми $k$ вершинами из первой
группы (с вершинами, образующими клику). Соответственно, $k$-антирасческой и $k$-веником
называются дополнения к $k$-расческе и $k$-гребешку.

\smallskip
\begin{center}
\begin{tabular}{ccccccccc}
\epsfig{figure=cispict.2}&$\quad$&\epsfig{figure=cispict.4}&$\quad$&\epsfig{figure=cispict.3}&$\quad$&\epsfig{figure=cispict.5}\\
\text{3-расческа}&&3-гребешок&&3-антирасческа&&3-веник
\end{tabular}
\end{center}
\smallskip



\z a)В $CIS$-графе любой $\Pi$-подграф содержится в $A$-подграфе (см. рисунок~3).

b)В $CIS$-графе для любой $k$-расчёски (являющейся подграфом) существует содержащий её
$k$-гребешок (являющийся подграфом исходного графа).

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.1}\\
\pic. $A$-граф
\end{tabular}
\end{center}


\z Приведите пример графа, в котором любая $k$-расчёска содержится в $k$-гребешке, любая
$k$-антирасчёска содержится в $k$-венике (для всех~$k$), а также в этом графе есть пара
непересекающихся максимальной клики и независимого множества.

\bigskip

{\bf Путеводная звезда.} Попробуйте доказать следующую важную теорему.

{\bf Теорема.} Пусть среди подграфов данного графа нет 3-расчёски и её дополнения, и все
$2$-расчёски дополнены до $2$-гребешков. Тогда этот граф является $CIS$-графом.

\bigskip
\centerline{\vrule height 1pt width 5cm}
\bigskip



{\bf Определение.} $d$-графом называется полный граф, каждое ребро которого покрашено в один из
$d$ цветов. Обозначим за $E_i$ рёбра $i$-го цвета. Граф на вершинах $d$-графа с рёбрами $E_i$
будем называть {\it хроматической} (или цветной) {\it компонентой} $i$-го цвета.

{\bf Определение $CIS$-$d$-графа.} Пусть для каждого цвета выбрано максимальное множество вершин,
среди которых любые две соединены ребром не этого цвета (максимальное означает, что при добавлении
любой другой вершины появляется ребро данного цвета%оно не содержится ни в каком другом, обладающим
%этим свойством\misha
%любая вершина
%не из этого множества соединена ребром выбранного цвета хотя бы с одной вершиной выбранного
%множества
\noindent). Пусть для любой такой выборки все эти независимые множества имеют общую вершину. Тогда
этот $d$-граф называется $CIS$-$d$-графом.

Рассмотрим игру на $d$ человек с полной информацией. Можно представлять ее себе как конечное
дерево, вершинами которого являются позиции в игре. Есть корневая вершина (начало игры). Из неё
выходят рёбра одного цвета (цвет игрока, который начинает игру). Тем самым игрок выбирает
следующую позицию в игре. Из любой новой вершины выходят рёбра также одного цвета (но другого%\marginpar{Обязятельно \\ другого?}
), причем для разных вершин этот цвет может быть разным. Тем самым первый игрок также выбирает,
кто будет ходить следующим. Далее аналогично. Так как дерево конечное, то игра когда-нибудь
закончится, то есть наступит один из исходов игры. Из вершины графа, соответствующей этой позиции,
больше ребер не выходит. Можно построить $d$-граф на вершинах-исходах, покрасив ребро между двумя
исходами в цвет исходящих ребер для вершины на пути, их соединяющем, ближайшей к корню.
%Рассмотрим вершину $u$, из которой
%выходят рёбра только к исходам. Пусть эти рёбра $k$-го цвета. Тогда соединим каждые два из этих
%исходов ребром $k$-го цвета. Рассмотрев все такие вершины $u$, мы разобьём множество исходов на
%группы, причём внутри каждой группы вершины попарно соединены. Далее мысленно представив все эти
%вершины $u$ исходами и,  повторив операцию, разобьем группы исходов на большие группы, причём
%внутри каждой большей группы исходы разных групп будут соединены одним и тем же цветом. Повторив
%эту операцию несколько раз, получим $d$-граф.
Оказывается, что получится $CIS$-$d$-граф (можете на досуге обдумать).


%Для $d=2$ определение $CIS$-$d$-графа выглядит так: $CIS$-2-графом (или просто $CIS$-графом)
%называется граф, в котором любая максимальная клика $C$ пересекается с любым максимальным
%независимым множеством $S$. Например, цикл длины четыре является $CIS$-графом, а $\Pi$-граф,
%изображённый на рисунке 1, не является $CIS$-графом.
У $CIS$-$d$-графа любая цветная компонента является $CIS$-графом (задача), но истинность обратного
утверждения неизвестна. Если дополнительно предположить, что в $CIS$-$d$-графе нет разноцветных
треугольников, то это обратное утверждение оказывается верным (задача). Описание таких
$CIS$-$d$-графов сводится к описанию $CIS$-графов (приемлемого описания нет ни у тех, ни у
других).

%%Сведение содержится в части 2.
%%Основная \marginpar{Повтор} идея в
%%следующем:

%%\smallskip



%{\bf Третье условие.} Если класс графов содержит некоторый граф, то полный граф
%на тех же вершинах также принадлежит этому классу.

%%\smallskip


%%Пусть $F$ --- класс графов, точно замкнутый относительно подстановки и замкнутый относительно
%%дополнения. Рассмотрим полный граф, каждое ребро которого покрашено в один из $d$ цветов так, что
%%не появилось разноцветного треугольника. Пусть все, кроме одной, цветные компоненты $d$-графа
%%принадлежат классу $F$. Тогда последняя цветная компонента также принадлежит классу $F$.

%Если также выполнено третье условие, то

%(b) любое из $2^d$ объединений некоторого числа цветных также принадлежит классу $F$.


\smallskip

Пока неизвестно, существует ли $CIS$-$d$-граф, в котором есть разноцветный треугольник, но если
вершин не больше 12, то нет разноцветного треугольника (проверено на компьютере).


{\bf Свойство графов Галлаи.}

%\setcounter{num}{0}
\smallskip

Назовём $\Delta$-графом граф на трёх вершинах, в котором три ребра покрашены в разные цвета
(разноцветный треугольник).
\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.10}\\
\pic. $\Delta$-граф
\end{tabular}
\end{center}

\smallskip

{\bf Определение.} $d$-граф, среди подграфов которого нет $\Delta$-графа, называется $d$-графом
Галлаи.

\smallskip

Переопределим $\Pi$-граф как $d$-граф на четырёх вершинах, в котором рёбра первого цвета образуют
букву $\Pi$, то есть хроматическая компонента первого цвета является $\Pi$-графом; остальные рёбра
покрашены во второй цвет, и рёбер остальных цветов нет. Будем его писать просто $\Pi$-граф.

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.9}\\
\pic. Цветной $\Pi$-граф
\end{tabular}
\end{center}
\smallskip

Цель этой части --- последняя задача, которая использует замечательное свойство $d$-графов
Галлаи~-- декомпозицию Галлаи. Декомпозиция Галлаи описана в задаче~\ref{decomp}.

\smallskip

\z Пусть дан $d$-граф $G$, обладающий следующим свойством: если в нём вычеркнуть рёбра любого
выбранного цвета, то он останется связным. Пусть $G$~--- это не $\Pi$-граф и не $\Delta$-граф.
Докажите, что из него можно выбросить одну вершину так, что он сохранит это свойство.


\smallskip

\z Пусть в $d$-графе ($d\geqslant3$) хроматическая компонента каждого цвета связна. Покажите, что
$\Delta$-граф является подграфом этого графа.


\smallskip

\z Проверьте, является ли класс $d$-графов Галлаи замкнутым относительно подстановки, точно
замкнутым относительно подстановки
%\marginpar{\bf ЗПТ?}
и является ли он наследственным.


\smallskip

\z\label{decomp} Докажите, что $d$-граф Галлаи является результатом подстановки $n$\, $d$-графов в
некоторый 2-граф вместо $n$ его вершин.


\smallskip

\z Пусть $F$~--- класс графов, точно замкнутый относительно подстановки и замкнутый относительно
дополнения. %Рассмотрим такой $d$-граф Галлаи, что все, кроме одной, его хроматические компоненты
%принадлежат классу $F$. Тогда последняя хроматическая компонента также принадлежит классу $F$.
Рассмотрим такой $d$-граф Галлаи, что все, кроме одной, его хроматические компоненты принадлежат
классу $F$ (пусть кроме компоненты цвета $d$). Предположим еще, что есть хотя бы одно ребро цвета
$d$. Тогда последняя хроматическая компонента также принадлежит классу $F$.
%Если также выполнено третье условие, то

%(b) любое из $2^d$ объединений некоторого числа хроматических компонент также принадлежит классу
%$F$.

\smallskip

\centerline{\vrule height 1pt width 5cm}

\begin{center} {\bf После промежуточного финиша.}
\end{center}
\bigskip

\begin{center}
{\bf $CIS$-$d$-графы Галлаи.}
\end{center}


\smallskip

\z Проверьте, является ли класс $CIS$-$d$-графов замкнутым относительно подстановки, точно
замкнутым относительно подстановки и является ли он наследственным.


\smallskip

\z Если среди подграфов данного $d$-графа нет $\Delta$-графов и $\Pi$-графов, то он является
$CIS$-$d$-графом.


\smallskip

\z Покажите, что $d$-граф, сопоставленный игре с полной информацией (см.~введение), не содержит
$\Delta$-графа и $\Pi$-графа, и что любой такой граф сопоставляется некоторой игре.


\smallskip

\z Приведите пример $d$-графа Галлаи, у которого есть рёбра хотя бы трёх цветов, но не являющегося
$CIS$-$d$-графом.


\smallskip

\z Приведите пример $CIS$-$d$-графа, у которого есть рёбра хотя бы трёх цветов.


\smallskip

\z $d$-граф Галлаи является $CIS$-$d$-графом, если и только если все его хроматические компоненты
являются $CIS$-графами.

\smallskip

\z Если все, кроме (может быть) одной, хроматические компоненты $d$-графа Галлаи являются
$CIS$-графами, то этот $d$-граф является $CIS$-$d$-графом.

\smallskip

\z Предположим, что все $CIS$-3-графы являются $3$-графами Галлаи. Тогда все $CIS$-$d$-графы
являются $d$-графами Галлаи.


\smallskip

\z {\bf Гипотеза.} Любой $CIS$-$d$-граф является $d$-графом Галлаи.

\bigskip

\begin{center}
{\bf Доказательство путеводной звезды.}
\end{center}

{\bf Определение.} Обозначим через $G_{10}$ граф, изображенный на рисунке:

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.6}\\
$G_{10}$
\end{tabular}
\end{center}
\smallskip


Обозначим через $2 G_{10}$ граф на двадцати вершинах $v_0,v_1,\dots,v_9,v_0',v_1',\dots,v_9'$,
составленный из двух копий~$G_{10}$ (первый граф $G_{10}$ на вершинах $v_0,v_1,\dots,v_9$, другой
--- на остальных), в котором для любых различных $i$ и $j$ вершины $v_i$ и $v_j'$ соединены, если и только если вершины $v_i$ и
$v_j$ не соединены. Любое ребро между вершинами $v_i$ и $v_i'$ может быть как проведено, так и
нет. Под $2 G_{10}$ будем подразумевать любой из этих 1024-ёх графов.

\smallskip

Граф, изображённый на следующем рисунке, называется графом Петерсена. Обозначим его $P$. Возьмём
две его копии с вершинами $u_1,u_2,\dots,u_{10}$ и $v_1,v_2,\dots,v_{10}$ соответственно. Соединим
вершины $u_i$ и $v_j$ ребром, если вершины $u_i$ и $u_j$ не соединены ребром для $i\neq j$. При
этом вершины $u_i$ и $v_i$ можем соединить ребром, а можем~--- нет. В результате получим
$2^{10}=1024$ графов. Запись ``граф $2P$'' подразумевает любой из них.

\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.7}\\
Граф Петерсена
\end{tabular}
\end{center}
\smallskip


%В графе $G_{10}$ нет 3-расчёски и её дополнения, но есть $\Pi$-подграфы,
%не содержащиеся в $A$-подграфах. Теорема, в частности, утверждает, что если мы начнём добавлять
%вершины и
%соединять с вершинами 2 и 3 $\Pi$-подграфов (то есть включать $\Pi$-подграфы в
%$A$-подграфы), то неизбежно появятся 3-расчёски.



%\noindent $CIS$-графы имеют широкое применение, но хорошего их описания пока нет. Например, согласно одной из задач
%они не описываются в терминах запрещённых подграфов, то есть нельзя сказать, что $CIS$-граф --- это такой граф,
%который не содержит каждый из графов $G_1,G_2,\dots$ ($G_1,G_2,\dots$ --- некоторые графы). Однако, близкие к ним
%$split$-графы согласно одной из задач --- это ровно те графы, которые не содержат в качестве подграфа цикл длины четыре,
%несвязное объединение двух отрезков и цикл длины пять. В частности такой класс графов является {\it наследственным},
%то есть любой подграф графа из этого класса также принадлежит этому классу. Такой класс образуют {\it совершенные} графы,
%то есть такие, число цветов правильной раскраски любого подграфа которых равно размеру максимальной клики в этом подграфе
%(наследственность очевидна). Также в 1971-ом году Lovasz доказал, что совершенные графы замкнуты относительно операции взятия
%{\it дополнения}, то есть дополнение совершенного графа --- снова совершенный граф. $CIS$-графы, очевидно,
%замкнуты относительно взятия дополнения. Кроме операций наследования и взятия дополнения удобно рассматривать
%операцию {\it подстановки}. А именно, в граф $G_1$ вместо вершины $v$ можно подставить граф $G_2$ так, что множество вершин полученного графа
%будет объединение множеств вершин графов $G_1$ и $G_2$ без вершины $v$, и если какая-то вершина графа $G_1$ была соединена с вершиной $v$,
%то она соединяется со всеми вершинами графа $G_2$; остальные рёбра сохраняются. Так вот, класс графов называется замкнутым
%относительно операции подстановки, если из графов $G_1$ и $G_2$ этого класса с помощью подстановки получается снова граф этого класса.
%И называется точно замкнутым относительно операции подстановки, если дополнительно потребовать, что графы этого класса могут получаться
%подстановкой только из графов этого класса. Классы совершенных графов и $CIS$-графов оказываются точно замкнутыми относительно подстановки и замкнутыми относительно дополнения, поэтому можно применить к ним общий результат:

%\noindent Пусть $F$ --- класс графов, точно замкнутый относительно подстановки и замкнутый относительно дополнения. Рассмотрим полный граф,
%каждое ребро которого покрашено в  один из $d$ цветов так, что не появилось разноцветного треугольника. Рассмотрим $d$ графов на вершинах этого полного графа, причём рёбра $i$-го графа --- это в точности рёбра $i$-го цвета. Пусть все, кроме одного, из этих графов принадлежат классу $F$. Тогда

%(a) последний рассмотренный граф также принадлежит классу $F$;

%(b) любое из $2^d$ объединений некоторого числа рассмотренных графов также принадлежит классу $F$.

%\noindent Понятие $CIS$-графа можно обобщить для полного графа с рёбрами нескольких цветов (если цветов два, то получается обычный $CIS$-граф). Есть давняя гипотеза, что в таком многоцветном графе также нет разноцветных треугольников. Если бы она была верна, то описание многоцветных $CIS$-графов сводилось бы к описанию обычных $CIS$-графов при помощи так называемой декомпозиции Галлаи, имеющей прямое отношение к сформулированному результату. Итак, предложенная задача о некоторых продвижениях в описании $CIS$-графов, постановке гипотезы и сведении многоцветного случая к обычным $CIS$-графам.

%\noindent{\bf Дополнительное задание. Почти-$CIS$-графы.}

%\setcounter{num}{1}
%\smallskip

%{\bf Определение.} {\it $Split$-графом} называется граф, в котором есть клика $C$ и независимое множетство $S$, такие что $C\cup S=V$, то есть в объединии дают всё множество вершин.

%{\bf Определение.} {\it Почти-$CIS$-графом} называется граф, в котором существует ровно одна пара непересекающихся максимальной клики $C$ и максимального независимого множества $S$.

%\bigskip

%\noindent{\bf \arabic{num}.}$Split$-граф является либо почти-$CIS$-графом, либо $CIS$-графом.

%\addtocounter{num}{1}
%\smallskip

%\noindent{\bf \arabic{num}.}a) Если граф является $split$-графом, то он не содержит в качестве подграфа ни цикла длины четыре, ни несвязного объединения двух отрезков (дополнение к циклу длины четыре), ни цикла длины пять.

%\noindent b) Покажите обратное, а именно: если в граф не содержит в качестве подграфа  ни цикла длины четыре, ни несвязного объединения двух отрезков, ни цикла длины пять, то этот граф является объединением некоторой клики и независимого множества.

%\noindent{\it Указание.} Можно действовать по индукции. Можно расширять множество $C\cup S$, где $C$ и $S$ --- некоторые клика и независимое множество.

%\addtocounter{num}{1}
%\smallskip
%\smallskip

%\noindent{\bf \arabic{num}.} Почти-$CIS$-граф яляется $split$-графом.

%\smallskip

%\noindentВ следующих двух подсказках $C$ и $S$ --- непересекающиеся максимальные клика и независимое множетсво графа $G$. Обозначим за $A$ множество вершин $V\ (C\cup S)$.

%\smallskip


%\noindent Подсказка 1. Пусть любая вершина из $A$ и $S$ соединены. Тогда постройте ещё одну пару непересекающихся максимальной клики и независимого множества.



%\noindent Подсказка 2. Пусть вершины $a\in A,b\in C$ и $c,d\in C$ таковы, что вершина $a$ соединена с вершинами $b$ и $c$, вершина $b$ --- с $a$ и $d$, вершина $c$ --- с $a$, вершины $a$ и $d$ не соединены, вершины $c$ и $b$ не соединены. Пусть также любая вершина из клики $C$ соединена либо с $a$, либо с $b$, и любая вершина из независимого множества $S$ не(!) соединена либо с вершиной $c$, либо с вершиной $d$.  Тогда постройте ещё одну пару непересекающихся максимальной клики и независимого множества.



%\newpage




\smallskip


{\bf Теорема.} Пусть среди подграфов данного графа нет 3-расчёски и её дополнения, и все
$2$-расчёски дополнены до $2$-гребешков. Тогда этот граф является $CIS$-графом.

В оставшихся задачах доказываем эту теорему.

\smallskip
\z{\bf В поисках $G_{10}$.} Пусть в графе $G$ есть хотя бы одна пара непересекающихся максимальной
клики $C$ и независимого множества $S$, среди подграфов данного графа нет 3-расчёски и её
дополнения, и все $2$-расчёски дополнены до $2$-гребешков.

a) Докажите, что есть вершины, не лежащие ни в $C$, ни в $S$.

b) Покажите, что граф $G$ содержит $G_{10}$.

%{\bf a)} Найдите в графе $G$ пару максимальных клики $C$ и независимого множества $S$ и две
%вершины $u$ и $v$ этой клики, такие что

%1) вершины $u$ и $v$ не имеют общих соседей в $S$

%2) для любых вершин $x$ и $y$ из $S$, таких что $x$ --- сосед $u$, $y$ --- сосед $v$, и для любой
%вершины $a$, такой что вершины $x,u,v,y,a$ образуют $A$-граф, вершины $a$ и $u$ имеют общего
%соседа в $S$ и вершины $a$ и $v$ имеют общего соседа в $S$

%{\bf b)} Покажите, что существуют две такие вершины $a$ и $a'$, что как в прошлом пункте вершины
%$x,u,v,y,a$ и $x',u,v,y',a'$ образуют $A$-графы и в $S$ есть две вершины $w$ и $w'$, такие что $w$
%соединена с $a$, но не соединена с $a'$, а $w'$ наоборот.

%{\bf c)} Докажите, что $G$ не существует.




%В следующих двух задачах доказываем:

%\z{\bf Лемма.} Нет графа, который удовлетворяет следующим трём свойствам:

%1) содержит граф $G_{10}$

%2) не содержит $3$-расчёски и её дополнения

%3) все $2$-расчёски содержатся в $2$-гребешках.

\smallskip
\z {\bf Найди второй!}

 %{\bf a)} Докажите, что существует только два графа, таких что:

%1) в графе 11 вершин

%2) подграф на первых 10-ти вершинах --- это $G_{10}$

%3) одиннадцатая вершина соединена с вершинами $v_4$ и $v_5$ и не соединена с вершинами $v_3$ и
%$v_6$

%4) в графе среди подграфов нет 3-расчёски и её дополнения

%\smallskip

 Пусть в графе $G$ все 2-расчёски содержатся в 2-гребешках, он содержит $G_{10}$ на вершинах $v_0,v_2,\dots,v_9$ и не
содержит 3-расчёску и её дополнение.

{\bf a)} Найдите в графе $G$ десять вершин $v'_0,v'_1,\dots,v'_9$ такие, что для любых различных
$i$ и $j$ вершины $v_i$ и $v'_j$ соединены ребром, если и только если вершины $v_i$ и $v_j$ не
соединены.

{\bf b)} Найдите в графе $G$ подграф $2G_{10}$.

%\smallskip

%{\bf b)} Найдите в графе $G$ вершину $v_7'$, которая для $i\neq7$ соединена с вершиной подграфа
%$G_{10}$ $v_i$, если и только если вершина $v_7$ не соединена с вершиной $v_i$.

%{\bf c)} Найдите в графе $G$ вершину $v_6'$, которая для $i\neq6$ соединена с вершиной подграфа
%$G_{10}$ $v_i$, если и только если вершина $v_6$ не соединена с вершиной $v_i$.

%{\bf d)} Докажите, что вершины $v_6'$ и $v_7'$ соединены ребром.

%{\bf e)} Найдите в графе $G$ вершину $v_1'$, которая для $i\neq1$ соединена с вершиной подграфа
%$G_{10}$ $v_i$, если и только если вершина $v_1$ не соединена с вершиной $v_i$.

%{\bf f)} Аналогично найдите вершины $v_2',v_3',v_4',v_5',v_8',v_9',v_0'$.

%{\bf g)} Докажите, что вершины $v_7'$ и $v_9'$ не соединены ребром.

%{\bf h)} Докажите, что вершины $v_6'$ и $v_0'$ не соединены ребром.

%{\bf i)} Докажите, что вершины $v_6'$ и $v_8'$ не соединены ребром.

%{\bf j)} Докажите, что вершины $v_6'$ и $v_9'$ не соединены ребром.

%{\bf k)} Докажите, что вершины $v_5'$ и $v_9'$ соединены ребром.

%{\bf l)} Покажите, что вершины $v_0',v_1',\dots,v_9'$ образуют $G_{10}$.

\smallskip


{\bf А где расчёски?} Заметим, что в любом графе $2G_{10}$ нет 3-расчёски и её дополнения, но зато
есть 2-расчёски, не вложенные в 2-гребешки, если предположить, что, например, вершины $v_2$ и
$v_2'$ соединены.

Далее предполагаем, что в графе $G$ все 2-расчёски содержатся в 2-гребешках, он содержит $2G_{10}$
и не содержит 3-расчёску и её дополнение.

\z {\bf a)} Покажите, что вершины подграфа $2G_{10}$ $v_2$ и $v_2'$ не соединены.

{\bf b)} Покажите, что вершины $2G_{10}$ можно перенумеровать так, что получится $2P$.

{\bf c)} Докажите теорему.

% по возможности уменьшить число пунктов или даже без пунктов

%\centerline{\vrule height 1pt width 5cm}


\section*{Решения}
Для краткости будем иногда называть независимое множество антикликой,
множество вершин графа $X$ будем обозначать через $V(X)$.

\setcounter{num}0

\sol \label{1} Возьмем в несвязном объединении графов $G_1$ и $G_2$ максимальное независимое
множество $S$ и максимальную клику $C$. Очевидно, что $S$ пересекается с каждым из графов $G_1$ и
$G_2$, а $C$ содержится в одном из них, скажем, в $G_1$. Тогда $S\cap G_1$ и $C\cap G_1$
пересекаются как максимальное независимое множество и максимальная клика в $G_1$, а значит,
пересекаются $S$ и $C$.


\sol \label{2} Если в \cis графе нет треугольников, то в нем нет $\Pi$-подграфов: иначе две
средние вершины этого подграфа образуют максимальную клику (обозначим ее $C$), а две крайние
вершины образуют независимое множество, которое не пересекается с $C$ и содержится в каком-то
максимальном независимом множестве, также не пересекающемся с $C$.

Рассмотрим любую компоненту связности нашего графа.
Если в ней есть две вершины
на расстоянии не меньше 3, то есть и две вершины на расстоянии ровно 3.
Кратчайший путь, их соединяющий, состоит из четырех вершин, и подграф на этих вершинах
является $\Pi$-графом, что невозможно.
Значит в каждой компоненте связности
любые две вершины соединены путем, в котором не более двух ребер.

Предположим, что в графе есть цикл нечетной длины, возьмем тогда
наименьший из них. В нем будет хотя бы 5 вершин, и пары его несоседних
вершин не будут соединены ребрами (иначе цикл делится на два меньших, один из которых
нечетный). Но тогда любые четыре подряд идущие вершины цикла образуют $\Pi$-граф, что невозможно.
Значит, нечетных циклов нет.
Несложно доказать, что такой граф является двудольным: его вершины можно разделить на две части так, что
у любого ребра концы будет лежать в разных частях.

Итак, каждая компонента связности является двудольным графом.
Он должен быть полным (любые две вершины из разных долей соединены): ведь длина кратчайшего пути между двумя
несоединенными вершинами из разных долей не меньше~3.
Таким образом, наш изначальный граф был
несвязным объединением нескольких полных двудольных графов.
Покрасить вершины такого графа в два цвета требуемым образом очень легко: в каждой компоненте
связности красим одну долю в первый цвет, а другую --- во второй.

Для завершения решения осталось проверить, что
любой такой граф удовлетворяет условию задачи.
Заметим, что раз полный граф является \cis
графом, то и полный двудольный граф (как дополнение к несвязному
объединению двух полных графов) тоже. Но тогда и любое несвязное объединение полных
двудольных графов является \cis графом.


В этом месте уместно сделать следующее очевидное замечание: граф является \cis графом тогда и только тогда,
когда любые клику и антиклику в нем можно дополнить до пересекающихся клики и антиклики.

\sol \label{3} Граф, получающийся из графа $G$ удалением вершины $v$ (и выходящих из нее ребер),
обозначим через $G-v$. Пусть $G$ был \cis графом, а $G-v$ нет, причем вершина $v$ была соединена в
графе $G$ с единственной вершиной $u$. Тогда в $G-v$ есть непересекающиеся максимальные клика $C$
и антиклика $S$. Дополним их соответственно до максимальной клики $C'$ и максимальной антиклики
$S'$ в графе $G$. Ясно, что $C'$ и $S'$ будут пересекаться только по вершине $v$. Но тогда в $C$
не может быть никаких вершин кроме $u$ (так как из $v$ выходит ребро лишь в вершину $u$). С другой
стороны,  если максимальная клика состоит из одной вершины, то эта вершина изолирована (то есть не
соединена с другими вершинами) и значит содержится в любой максимальной антиклике. Поэтому  $C$ и
$S$ пересекаются по вершине $u$. Противоречие.


\sol  \label{4} а) Предположим противное, тогда в графе $G$ есть непересекающиеся максимальные
клика $C$ и независимое множество $S$, а в $C$ есть хорошая вершина $v$. Если существует вершина
$u\in V(S)$, соединеная с $v$, то все вершины $C$ смежны с $u$ (т.к. $v$ хорошая), что
противоречит максимальности $C$. Значит $v$ не соединена ни с одной вершиной $S$, но это
противоречит максимальности $S$.
\par b) Примером служит цикл длины 4.


\sol  \label{5} Пусть граф является объединением пересекающихся клики $C$ и независимого множества
$S$. Ясно, что $C$ и $S$  пересекаются ровно по одной вершине (назовем ее $u$). Рассмотрим любую
максимальную клику $C'$. Если она содержит вершину из $S$, то ровно одну, и эта вершина является
хорошей (поскольку все ее соседи лежат в клике $C$). Если же все вершины $C'$ лежат в $C$, но не в
$S$, то в силу максимальности $C'$ получаем $C'=C$, и значит в $C'$ все-таки есть вершина из $S$,
а именно $u$ --- противоречие. Итак, в любой клике нашего графа есть хорошая вершина --- значит он
является \cis графом по задаче 4.
%Пусть граф является объединением пересекающихся клики $C$ и независимого множества $S$.
%Ясно, что $C$ и $S$ максимальны и пересекаются ровно по одной вершине (назовем ее $u$).
%Теперь предположим, что какие-то максимальные клика $C'$ и антиклика $S'$ не пересекаются. Если $C'=C$,
%а $S'$ не пересекается с $C'$, то $S'\subset S$, следовательно, $S'=S$, что противоречит тому, что $C'$
%и $S'$ не пересекаются. Значит, $C'\ne C$ и (по аналогичным причинам) $S'\ne S$. Пусть $s \in V(C')\setminus V(C)$,
%$c \in V(S')\setminus V(S)$; не умаляя общности будем считать, что ребро между $c$ и $s$ отсутствует. Но т.к. $S'$
%максимальна, в ней должна существовать смежная с $s$ вершина $c'$. Заметим, что $c'$ не может лежать в $S$ (там уже
%лежит $c'$ и это антиклика). Значит, $c'$ лежит в $C$. Таким образом, клика $C$ и антиклика $S'$ имеют в пересечении
%вершины $s$ и $c'$, чего не может быть (ребро $(s,c')$ дожно присутствовать и отсутствовать одновременно).


\sol  \label{6} Пусть $G$ --- граф, полученный подстановкой $G_1$ в $G_2$. Разберем два случая.

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


Пусть $G_2$ не был \cis графом,
тогда в нем найдутся непересекающиеся максимальная клика $C$ и независимое множество $S$.
Заметим, что вершина, которую мы заменяем на граф $G_1$, не может лежать сразу и в $C$, и в $S$.
Поэтому после подстановки один из графов $C$ и $S$ (например $C$), не изменится (и останется максимальной кликой),
а другой ($S$) либо тоже не изменится (и останется максимальной антикликой), либо в нем одна вершина заменится на $G_1$ (тогда остальные вершины
$S$ вместе с любой максимальной антикликой $G_1$ дадут максимальную антиклику $S'$).  В любом случае находим непересекающиеся клику и антиклику
в $G$ --- противоречие.

Значит и $G_1$, и $G_2$ были \cis графами, что и требовалось доказать.

%Для доказательства того, что $G_2$ не может не быть \cis графом достаточно заметить, что при операции,
%обратной к подстановке, клики и антиклики переходят в клики и антиклики и, более того, все клики и антиклики $G_2$ таким образом получаются.


\sol  \label{7} Рассмотрим произвольный граф $G$ и для каждой его максимальной клики дорисуем к
графу вершину и соединим её со всеми вершинами этой клики и только с ними (процедуру следует
проделать один раз). В полученном графе (по построению) каждая максимальная клика содержит ровно
одну добавленную вершину, которая, очевидно, хорошая. Таким образом (по задаче 4) полученный граф
является \cis графом, а исходный является его подграфом


\sol  \label{8}
%a) Пусть из клика $C$ и антиклика $S$ -- индуцированные подграфы графа $G$, причем $V(G)=V(C)\sqcup V(S)$ и каждая вершина $C$
%смежна хотя бы с одной вершиной $S$, и наоборот, каждая вершина $S$ не смежна хотя бы с одной вершиной $C$ (т.е. $C$ и $S$ максимальны в $G$).
%Тогда будем называть {\it достраиванием} граф $H$, полученный добавлением к $G$ вершины, смежной со всеми вершинами клики и только с ними.
%Перенумеруем все возможные четверки, $G,C,S,H$, получится четыре последовательности $\st {G_i}$,$\st {S_i}$,$\st {S_i}$,$\st {H_i}$.

%Заметим, что  граф не является \cis графом, тогда и только тогда (в силу замечания), когда в нем можно выделить клику и антиклику,
%к которым в графе нет достроения, то есть, содержащий подграф, изоморфный $G_i$ (для некоторого $i$), недостраиваемый до подграфа,
%изоморфного $H_i$. Таким образом, последовательности $G_i$, $H_i$ удовлетворяют условию.

а) Рассмотрим все возможные графы, являющиеся объединением непересекающихся максимальных клики и независимого множества.
Все такие графы получаются следующим способом: рисуем клику $C$, рисуем независимое множество $S$, после чего каждую вершину $C$
соединяем хотя бы с одной вершиной $S$ (но не со всеми сразу).
Занумеруем эти графы натуральными числами (например, так: сначала нумеруем (в произвольном порядке)
такие графы из трех вершин, потом --- из четырех, и так далее; на каждом шаге число нумеруемых графов будет конечным).
Граф с номером $i$ обозначим через $G_i$.
Тогда $H_i$ строим так: добавляем к $G_i$ одну вершину и соединяем ее со всеми вершинами
максимальной клики $G_i$ (и только с ними). При этом никакой $C_i$ не будет \cis графом, зато каждый $H_i$ будет \cis графом.

Ясно, что любой \cis граф $G$, содержащий $G_i$, содержит и $H_i$ --- достаточно дополнить клику и антиклику в $G_i$ до максимальных
в $G$, и мы получим вершину, соединенную с кликой из $G_i$ и не соединенную с антикликой из $G_i$ (то есть получим $H_i$).

И наоборот, если есть граф $G$, не являющийся \cis графом, то в нем есть максимальные клика и антиклика, которые не пересекаются.
Подграф на их вершинах будет одним из $G_i$ и очевидно не будет дополняться до $H_i$.


\par b) Предположим, что существует такой конечный набор, будем считать, что максимальное количество вершин в графах $G_i$, $H_i$
равно $n$. Рассмотрим тогда $n$-расческу и $n$-гребешок. Несложно проверить, что если в гребешке любой $G_i$ дополняется до $H_i$,
то и в расческе тоже. Однако гребешок явялется \cis графом, а расческа -- нет. Противоречие.
%и антиклики (это означает, что каждая вершина клики соединена хотя бы с одной вершиной антиклики, каждая вершина антиклики не соединена хотя бы с одной вершиной клики и нет вершины, не содержащейся в клике и антиклике ).

%Переупорядочим все графы, состоящие из непересекающихся клики, антиклики и, возможно, некоторых ребер между ними в последовательность $G_i$.
%Теперь очевидно, что каждый не \cis граф имеет в качестве подграфа граф $G_i$


%Множеством графов $G_i$ будет множество графов, множество вершин которых является объединеним максимальных клики $C_i$ и антиклики $S_i$, то есть каждая вершина клики соединена хотя бы с одной вершиной антиклики, и каждая вершина антиклики не соединена хотя бы с одной вершиной клики. Графом $H_i$ будет граф $G_i$, к которому добавлена одна вершина, соединённая со всеми вершинами максимальной клики $C_i$ и только с ними.

%Пусть дан граф $G$, в котором каждый подграф $G_i$ дополняется до подграфа $H_i$.



\sol  \label{9} a) Пусть клика $C$ и независимое множество $S$ в объединении дают весь граф $G$,
кроме вершины $v$. Пусть $C'$ -- это множество смежных с $v$ вершин $S$, а $S'$ -- это множество
несмежных с $v$ вершин $S$. Тогда клика $C'\cup v$ должна дополняться до максимальной клики,
пересекающейся с $S$, следовательно, существует вершина $s\in S'$, смежная со всеми вершинами $C'$
и с вершиной $v$. Аналогично, существует вершина $c\in C'$, не смежная со всеми вершинами $S'$ и
не смежная с вершиной $v$. Не умаляя общности, ребро $(s,c)$ проведено, тогда найдем в $C$ вершину
$c'$, не смежную с $s$ (она по построению не будет соединена с $v$). Теперь осталось посмотреть на
максимальную клику, состоящую из всех смежных с $s$ вершинами и на любое максимальное независимое
множество, содержащее $c'$ и $v$, убедиться в том, что они не могут пересекаться ни по вершине $v$
(потому, что она не соединена с лежащей в клике $c'$), ни внутри $C$ (потому, что $c'$ не смежна с
$s$), ни внутри $S$ (потому, что $s$ смежна с $v$).

b),c) См. статью cis1.pdf.

\sol  \label{10}  a) ({\it Решение предложено командой Василия Мокина, Виктора Омельяненко и
Виктора Садкова.}) Назовем эту пару множеств $C$ и $S$ и рассмотрим  полный ориентированный
двудольный граф с множеством вершин $V(C)\cup V(S)$ и ребрами, проведенными по правилу: если в
исходном графе вершины $c\in C$ и $s \in S$ были смежны, то в новом графе ребро будет идти от $c$
к $s$, в противном случае от $s$ к $c$. Так, как $S$ была максимальной антикликой, любая вершина
остального графа была смежна хотя бы с одной вершиной $S$, в частности это означает, что в новом
графе из любой вершины $C$ выходит (в ориентированном смысле!) хотя бы одно ребро. Аналогично, из
любой вершины $S$ так же выходит хотя бы одно ребро.
\par Таким образом, в нашем ориентированном графе исходящяя степень каждой вершины не меньше 1, следовательно, в нем есть цикл (под циклом в ориентированном графе понимаем ориентированный цикл). Тогда рассмотрим цикл наименьшей длины $A_1A_2\dots A_{2n}$ (длина четная так, как граф был двудолен), если $2n>4$, то в зависимости от ориентации ребра $A_1A_4$ в графе можно найти либо цикл $A_1A_2A_3A_4$, либо $A_1A_4A_5\dots A_{2n}$, меньший минимального. Значит, $2n=4$. Тогда несложно проверить, что в исходном графе на вершины $A_1$, $A_2$, $A_3$, $A_4$ индуцировался $\Pi$-граф.

\par b) Например, $A$-граф, он же 2-гребешок.

\sol  \label{11} a) Является частным случаем нижеследующего пункта
\par b) рассмотрим любую максимальную клику, содержащую первую группу вершин расчески (они образуют клику) и
любую максимальную антиклику, содержащую вторую группу вершин расчески (они образуют антиклику). В их
пересечении будет хотя бы одна вершина, которая при добавлении к расческе даст веник.


\sol % 12
\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.11}\\
\pic\label{1}
\end{tabular}
\end{center}

\noindent{\bf Основное свойство графов Галлаи.}

\setcounter{num}{12}

\sol % 13
Пусть в условии дан $d$-граф $G$, а $v$~--- некоторая его вершина. Заметим, что найдётся не более
одного цвета такого, что удаление из $G$ вершины $v$ влечёт несвязность на рёбрах не этого цвета:
если при удалении первого цвета $G$ станет несвязным, то все ребра между компонентами связности
должны быть обязательно первого цвета, а полный двудольный граф связен, и тогда при удалении
любого другого цвета оставшийся граф будет связным. Предположим, что для любой вершины найдётся
цвет такой, что граф без этой вершины на рёбрах не этого цвета несвязен. Таких цветов не может
быть больше одного, поэтому покрасим вершину в этот цвет.

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

Пусть есть вершина $u$ первого цвета. Пусть $v_1,v_2,\dots,v_n$ и $w_1,w_2,\dots,w_m$~-- какое-то
разбиение остальных вершин графа на два множества, между которыми потеряется связь при выкидывании
первого цвета (если вершину $u$ уже выкинули). Все ребра между этими двумя группами первого цвета.
Эти два множества будем называть кусками; кусок, в котором хотя бы две вершины, будем называть
большим. Если оба куска маленькие, то либо данный $d$-граф~--- это разноцветный треугольник, либо
он не удовлетворяет свойству в условии. Пусть есть хотя бы один большой кусок. Вершин не первого
цвета как минимум две, а маленький кусок может содержать максимум одну вершину не первого цвета,
поэтому хотя бы один большой кусок содержит вершину не первого цвета. Не умаляя общности,
предположим, что это второй кусок, то есть $m\geqslant 2$ и вершина $w_1$ второго цвета. Теперь
проделаем ту же процедуру для второго цвета. Вершины графа разбиваются на два куска, между
которыми все рёбра второго цвета. Так как рёбра
$(w_2,v_1),(w_2,v_2),\dots,(w_2,v_n),(v_1,w_3),(v_1,w_4),\dots,(v_1,w_m)$ первого цвета, то
вершины $w_2,v_1,v_2,\dots,v_n,w_3,\dots,w_m$ в одном куске относительно $w_1$. Значит, вершина
$u$ в другом куске, и из вершины $u$ во все вершины, кроме $w_1$, выходят рёбра второго цвета.

Рассмотрим вторую вершину $w_1'$ цвета $k\neq1$. Проделаем для нее то же самое, что и для $w_1$,
то есть разобьем остальные вершины на два куска. Посмотрим еще, в какой кусок относительно $u$ она
попала. Если в большой, то аналогично вершина $u$ соединена со всеми вершинами, кроме $w_1'$,
рёбрами цвета $k$, но в графе есть еще вершины, кроме $u$, $w_1$, $w_1'$ (т.к. в графе хотя бы 4
вершины). Так как в них из $u$ ведут ребра одновременно цвета $2$ и $k$, то $k=2$. Получается, что
из вершины $u$ выходят рёбра только второго цвета. Значит, данный $d$-граф несвязен на рёбрах не
второго цвета. Получаем, что $w_1'=v_1$, $n=1$ и вершины $w_2,w_3,\dots,w_m$ первого цвета.


\smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.14}\\
\pic\label{1}
\end{tabular}
\end{center}


Удалим $w_2$. Вершины графа разбились на две группы вершин, между которыми рёбра первого цвета.
Так как рёбра $(u,v_1),(u,w_2),(u,w_3),\dots,(u,w_m)$ второго цвета, то вершины
$u,v_1,w_3,\dots,w_m$ в одной группе. Значит, $w_1$ в другой. Получаем, что вершина $w_1$
соединена с вершинами $u,v_1,w_3,w_4,\dots,w_m$ рёбрами первого цвета. Если $m>2$, то аналогично
получаем, что ребро $(w_1,w_2)$ первого цвета, то есть из вершины $w_1$ выходят рёбра только
первого цвета~--- противоречие. Тогда $m=2$. Если ребро $(w_1,w_2)$ второго цвета, то данный
$d$-граф является $\Pi$-графом. Если ребро $(w_1,w_2)$ первого цвета, то данный $d$-граф на рёбрах
не первого цвета несвязен~--- противоречие.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55


\sol\label{treug} %14
Индукция по количеству вершин. База, скажем, для $n=3$: очевидно, один из цветов несвязен.
Переход. Пусть $n>3$ и все цвета связны. Выбросим одну из вершин (назовем ее $a$); если связность
не нарушилась, то по предположению индукции треугольник нашелся. Значит, какой-то (скажем, 1) цвет
потерял связность. Пусть $C_1,\dots,C_k$~--- компоненты связности первого цвета в полученном
графе; заметим, что $a$ была соединена с любой из них ребром первого цвета.

Рассмотрим $C_i$ и $C_j$ и ребро, соединяющее две их вершины $c_i$ и $c_j$; оно, б.о.о., имеет
цвет 2. Тогда, если вершина $c_i'$ (из $C_i$) связана  c $c_j$ ребром 3 цвета, то образовался
разноцветный треугольник; значит, ребро $c_i'-c_j$ также второго цвета. Продолжая так далее,
получаем, что для любых двух компонент $C_i$ и $C_j$ все ребра между ними одноцветны.

Вернемся к исходному графу. Из связности следует, что $a$ соединена ребрами цветов 2 хоть с
кем-то. Пусть она соединена ребром 2 с вершиной $c_r\in C_r$. Если из $C_r$ хоть в какую-то $C_s$
ведут ребра 3 цвета, то найдем вершину $c_s\in C_s$ такую, что $a-c_s$ цвета 1 (такая, напомним,
найдется из связности); тогда $a,c_r,c_s$ образуют искомый треугольник.

Итак, из $C_r$ во все другие компоненты ведут ребра только 2 цвета. Аналогично, рассмотрев
компоненту $C_t$, в которую из $a$ ведет ребро 3 цвета, мы получим, что из $C_t$ в другие
компоненты ведут только ребра 3 цвета. Это невозможно ни в случае $r=t$ (так как есть еще какие-то
компоненты, и непонятно, ребра какого цвета туда идут из $C_r$), ни в случае $r\ne t$ (тогда
непонятно, какого цвета ребра между $C_r$ и $C_t$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\noindent{\bf Лемма 1.} Пусть в $d$-графе без разноцветных треугольников первая хроматическая
%компонента связна. Пусть вершина $u$ из $C_1$ не соединена ребром первого цвета ни с одной из
%вершин $v,w_1,w_2,\dots,w_n$. Пусть ребро $(v,u)$ второго цвета. Тогда, если взять вершину из
%$C_1$ и вершину не из $C_1$, то ребро между ними будет первого или второго цвета.
%
%\noindent{\bf Доказательство.} Вершины не из $C_1$ поделим на три группы: вершина $v$, вершины из
%$C_2,\dots,C_k$ и вершины $w_1,w_2,\dots,w_n$. И в этом порядке будем доказывать, что ребро
%проведённое от них к вершине из $C_1$ либо первого, либо второго цвета.
%
%1) Пусть $u,u_1,u_2,\dots,u_m$ --- путь в $C_1$ из рёбер первого цвета. Рассмотрим неразноцветные
%треугольники $(v,u,u_1),(v,u_1,u_2),\dots,(v,u_{m-1},u_m)$. Ребро (v,u) второго цвета, ребро
%$(u,u_1)$ первого цвета, а ребро $(v,u_1)$ не первого цвета, значит, ребро $(v,u_1)$ второго
%цвета. Аналогично все рёбра $(v,u_i)$ второго цвета для $i=1,2,\dots,m$. Значит, любое ребро между
%вершиной $v$ и вершиной из $C_1$ второго цвета.
%
%2) Рассмотрим путь из рёбер первого цвета от вершины $v$ до любой вершины не из $C_1$, не
%проходящий через вершины $C_1$. Аналогично, вершина $u$ соединена с вершинами пути рёбрами второго
%цвета. А так как первая хроматическая компонента связна, то вершина $u$ соединена с любой вершиной
%не из $C_1$ ребром второго цвета.
%
%Теперь рассмотрим произвольную вершину $u'$ из $C_i,i\neq1$ и путь из рёбер первого цвета в $C_1$
%от вершины $u$. Вершины $u$ и $u'$ соединены ребром второго цвета, следовательно аналогично
%предыдущему вершина $u'$ соединена со всеми вершинами выбранного пути рёбрами второго цвета, а
%значит и со всеми вершинами $C_1$ рёбрами второго цвета.
%
%3) Рассмотрим вершину $u_1$ из $C_1$ и треугольник $v,w_i,u_1$. Ребро $(v,w_i)$ первого цвета,
%ребро $(v,u_1)$ второго цвета, значит, ребро $(w_i,u_1)$ первого или второго цвета.
%
%\noindent Мы получили, что ребро между вершиной из $C_1$ и вершиной не из $C_1$ первого или
%второго цвета, значит, третья хроматическая компонента несвязна, и мы имеем
%
%\noindent{\bf Следствие.} В $d$-графе без разноцветных треугольников, все хроматические компоненты
%которого связны,  любые две вершины в любой хроматической компоненте либо соединены, либо имеют
%общего соседа.
%
%
%\smallskip
%
%Тогда, в частности, любая вершина в графе соединена с одной из вершин $w_1,w_2,\dots,w_n$ ребром
%первого цвета. Для любой вершины $u$ обозначим за $N(u)$ множество вершин среди вершин
%$w_1,w_2,\dots,w_n$, соединённых с ней ребром первого цвета. Обозначим за $A$ множество всех
%вершин графа, кроме вершин $v,w_1,w_2,\dots,w_n$.
%
%\noindent{\bf Замечание.} Любая вершина из $A$ соединена с вершиной $w_i$ либо ребром первого
%цвета, либо того же цвета, что и с вершиной $v$.
%
%\smallskip
%
%\noindent{\bf Лемма 2.} Рассмотрим $d$-граф (не имеющий отношения к данному в задаче графу) на
%пяти вершинах $v,w_1,w_2,a_1,a_2$ (некоторые обозначения сохранены, но это уже другие вершины), в
%котором нет разноцветных треугольников, рёбра $(v,w_1),(v,w_2),(w_1,a_1),(w_2,a_2)$ первого цвета,
%рёбра $(v,a_1),(w_2,a_1)$ одного цвета, но не первого, и рёбра $(v,a_2),(w_1,a_2)$ одного цвета,
%но не первого цвета, а про остальные рёбра ничего не известно. Тогда рёбра $(v,a_1)$ и $(v,a_2)$
%одного цвета.
%
%
%\noindent{\bf Доказательство.}  Если ребро $(a_1,a_2)$ первого цвета, то рассмотрим неразноцветный
%треугольник $(v,a_1,a_2)$ и получим, что рёбра $(v,a_1)$ и $(v,a_2)$ одного цвета. Если ребро
%$(a_1,a_2)$ не первого цвета, то рассмотрим неразноцветный треугольник $(w_1,a_1,a_2)$ и получим,
%что рёбра $(w_1,a_2)$ и $(a_1,a_2)$ одного цвета; аналогично рёбра $(w_2,a_1)$ и $(a_1,a_2)$
%одного цвета, а значит и рёбра $(w_2,a_1)$ и $(w_1,a_2)$ одного цвета, следовательно рёбра
%$(v,a_1)$ и $(v,a_2)$ одного цвета.
%
%\noindent{\bf Следствие.} Пусть для двух вершин $a_1$ и $a_2$ из $A$ верно (обозначения
%вернулись), что $N(a_1)$ не вложено в $N(a_2)$ и наоборот. Тогда рёбра $(v,a_1)$ и $(v,a_2)$
%одного цвета.
%
%\noindent{\bf Доказательство.} Можно выбрать вершины $w_i$ и $w_j$, такие что рёбра $(w_i,a_1)$ и
%$(w_j,a_2)$ первого цвета, а рёбра $(w_i,a_2)$ и $(w_j,a_1)$ не первого. По замечанию и по лемме 2
%(вершины $w_i$ и $w_j$ выступают в качестве $w_1$ и $w_2$) получаем, что рёбра $(v,a_1)$ и
%$(v,a_2)$ одного цвета.
%
%\smallskip
%
%По следствию из леммы 1 от вершины $v$ можно добраться до вершины $w_i$ не более, чем по двум
%рёбрам второго цвета, то есть вершина $w_i$ соединена хотя бы одним ребром второго цвета с одной
%из вершин из $A$. Также для третьего цвета. Пусть $A=\{a_1,a_2,\dots,a_k\}$. Рассмотрим множества
%вершин $N(a_1),N(a_2),\dots,N(a_k)$. Их пересечение пусто. Некоторые из них можно убрать так,
%чтобы среди оставшихся для любых двух одно не вложено в другое, и пересечение всех также пусто.
%Пусть остались $N(a_1),N(a_2),\dots,N(a_l)$. Тогда по следствию из леммы 2 все рёбра
%$(v,a_1),(v,a_2),\dots,(v,a_l)$ одного цвета. Выберем вершину $a'$ такую, что ребро $(v,a')$
%третьего цвета. По следствию из леммы 2 каждое $N(a_i),i=1,2,\dots,l$ либо содержит, либо
%содержится в $N(a')$. $N(a')$ не может содержаться во всех $N(a_i),i=1,2,\dots,l$, потому что их
%пересечение пусто. Тогда оно содержит некоторое $N(a_s)$ из них. Но если какое-то другое $N(a_r)$
%содержит $N(a')$, то $N(a_r)$ содержит $N(a_s)$ --- противоречие. Значит, $N(a')$ содержит все
%$N(a_i),i=1,2,\dots,l$. Возьмём любое $w_i$ из $N(a_1)$. Для любого $a'$, для которого ребро
%$(v,a')$ третьего цвета, по доказанному ребро $(w_i,a')$ первого цвета. Значит, по замечанию, из
%вершины $w_i$ в вершины множества $A$ не выходит рёбер третего цвета, что противоречит тому, что
%вершины $w_i$ и $v$ имеют общего соседа по третьему цвету.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\sol %15
Аналогично решению задачи 6 получаем, что данный класс замкнут относительно подстановки. Заметим,
что для любой вершины $d$-графа можно рассмотреть набор из $d$ максимальных множеств, каждое из
которых свободно от ребер какого-то своего цвета. Из этого выводится, что данный класс точно
замкнут. При $d=2$, очевидно, этот класс не наследственный.
%%%%%%%%%%%%%%%

\sol% 16
\noindent{\bf Утверждение.} Пусть в $d$-графе Галлаи есть хотя бы одно ребро $d$-го цвета и
хроматическая компонента $d$-го цвета несвязна. Тогда все рёбра между двумя любыми фиксированными
компонентами связности этой хроматической компоненты покрашены в один и тот же цвет.

\noindent См. решение задачи~\ref{treug}.
%Рассмотрим две компоненты связности $C_1$ и $C_2$ $d$-ой хроматической компоненты и выберем из
%каждой по вершине. Пусть ребро между выбраннымим вершинами $u$ и $v$ первого цвета. Пусть $w$ ---
%сосед (по $d$-ому цвету) вершины $u$ в $C_1$. Рёбра $(u,v)$ и $(w,v)$ не $d$-го цвета, потому что
%из вершин $C_1$ нельзя добраться до вершин $C_2$ по рёбрам $d$-го цвета. А ребро $(u,w)$ $d$-го
%цвета и треугольник $(u,v,w)$ неразноцветный, значит, рёбра $(u,v)$ и $(w,v)$ одного цвета.

\noindent {\bf Решение задачи.} Будем доказывать спуском по $k$ ($k<d$) следующее утверждение.
Пусть дан $d$-граф Галлаи. Тогда он является результатом подстановки $d$-графов
$G_1,G_2,\dots,G_n$ вместо $n$ вершин $k$-графа $G$% ($k\geqslant3$)
, причем у $G$ как минимум две вершины.

Очевидно, для $k=d$ утверждение верно. Пусть для какого-то $k$ утверждение верно, докажем его для
$k-1$. Возьмем $d$-граф Галлаи и построим для него по предположению спуска разложение для $k$. По
прошлой задаче, этот $k$-граф и все графы $G_1,G_2,\dots,G_n$ являются $d$-графами Галлаи. По
задаче 2 хроматическая компонента некоторого цвета $k$-графа $G$ несвязна. Пусть это $k$-ый цвет и
$C_1,C_2,\dots,C_m$~--- компоненты связности этой хроматической компоненты. Обозначим $F_i$
подграф графа $G$ на вершинах $C_i$. Тогда по лемме граф $G$ является результатом подстановки
графов $F_1,F_2,\dots,F_m$ вместо $m$ вершин некоторого $(k-1)$-графа $H$. Осталось подставить
графы $G_1,G_2,\dots,G_n$ вместо вершин графов $F_1,F_2,\dots,F_m$ (если $C_i$ состоит из
$i_1$-ой, $i_2$-ой, $\dots$, $i_p$-ой вершин, то в $F_i$ нужно подставлять графы
$G_{i_1},G_{i_2},\dots,G_{i_p}$ согласно номерам вершин). Пусть мы получили графы
$H_1,H_2,\dots,H_m$. Тогда исходный $d$-граф Галлаи является результатом подстановки $d$-графов
$H_1,H_2,\dots,H_m$ вместо вершин $(k-1)$-графа $H$. При $k=2$ получаем требуемое утверждение.

\sol \begin{lemma} \label{treug1}%17
Предположим, что у данного в условии графа Галлаи есть рёбра
цвета $d$ и $d\geqslant3$. Тогда граф на $n$ вершинах без рёбер принадлежит классу $F$.
\end{lemma}

\begin{proof}
Если в классе $F$ есть хотя бы один несвязный граф, то граф из двух вершин без ребра также
принадлежит классу $F$, потому что такой граф является результатом подстановки двух графов в граф
из двух вершин без ребра, среди которых первый граф --- это первая компонента связности, а
второй~--- всё остальное. После этого граф из двух вершин без ребра можно подставить в себя
несколько раз и получить искомый.

Докажем индукцией по числу вершин данного в условии $d$-графа Галлаи~$G$, что классу $F$
принадлежит некоторый несвязный граф. По прошлой задаче $G$  можно получить, подставив некоторые
$d$-графы $G_1,G_2,\dots,G_n$ вместо $n$ вершин некоторого 2-графа $H$ с $\geqslant2$ вершинами.
Это индуцирует подстановки на всех хроматических компонентах исходного графа. Либо в одном из
$G_i$, либо в $H$ есть рёбра цвета $d$. Класс $F$ точно замкнут, поэтому условия утверждения верны
для найденного $G_i$ (либо для $H$). Применим к нему предположение индукции, получим требуемое.
Осталось проверить базу. Возьмём граф на на двух вершинах с ребром цвета $d$. Компонента первого
цвета несвязна.
\end{proof}

Будем решать исходную задачу индукцией по числу вершин.

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

Шаг. Пусть встречаются рёбра не более двух цветов. По условию все цветные компоненты, кроме $d$-й,
принадлежат классу $F$. Мы знаем, что в $G$ есть хотя бы одно ребро цвета $d$. В силу того, что
класс графов $F$ замкнут относительно дополнения, последняя (=вторая нетривиальная) цветная
компонента также принадлежит классу $F$. Пусть встречаются рёбра как минимум трёх цветов. Тогда по
прошлой задаче данный $d$-граф Галлаи $G$ можно получить, подставив некоторые $d$-графы
$G_1,G_2,\dots,G_n$ вместо $n$ вершин некоторого 2-графа $H$ с $\geqslant2$ вершинами.
Хроматическая компонента $i$-го цвета графа $G$~--- это результат подстановки хроматических
компонент $i$-го цвета $d$-графов $G_1,\dots,G_n$ вместо вершин $i$-ой хроматической компоненты
$d$-графа $H$ ($2$-граф можно рассматривать как $d$-граф, у которого есть рёбра только двух
цветов). По условию все, кроме одной, хроматические компоненты $d$-графа $G$ принадлежат классу
$F$. Так как класс $F$ точно замкнут относительно подстановки, все хроматические компоненты, кроме
компоненты цвета $d$, $d$-графов $H,G_1,G_2,\dots,G_n$ принадлежат классу $F$. У каждого из этих
графов меньше вершин. Поэтому по предположению индукции и по лемме~\ref{treug1} хроматическая
компонента цвета $d$ каждого из этих графов также принадлежит классу $F$. Так как класс $F$
замкнут относительно подстановки, то $d$-я цветная компонента $d$-графа $G$ также принадлежит
классу $F$.


{\bf $CIS$-$d$-графы Галлаи.}

\smallskip
\setcounter{num}{17}

\sol   Аналогично решению задачи 6.%18

\sol   Следует из задач 10 и 23.

\sol %20
Если $x,y$ -- висячие вершины, будем обозначать $P(x,y)$ ближайшую к корню вершину на соединяющем
их пути (она еще называется их наименьшим общим предком). Несложно проверить, что для любых
исходов (то есть висячих вершин) $x$, $y$, $z$ среди вершин $P(x,y)$, $P(y,z)$, $P(z,x)$ хотя бы
две совпадают. Таким образом, хотя бы два из ребер $(x,y)$, $(y,z)$, $(z,x)$ имеют один цвет.
Аналогично (проверяется небольшим перебором) можно проверить, что нельзя выделить в дереве четыре
вершины и покрасить их наименьших общих предков так, чтобы на выделенных четырех вершинах
образовался $\Pi$-граф. {\bf В обратную сторону } доказательство индукцией по количеству вершин.
База очевидна. Переход: как мы знаем из задачи 13, существует цвет (пусть первый), при удалении
ребер которого граф перестает быть связным (но все компоненты, разумеется, остаются свободными от
$\Delta$, $\Pi$). Тогда для каждой компоненты связности можно построить по дереву (по
предположению индукции), несвязно их объединить и добавить вершину, соединенную со всеми корнями
этих деревьев исходящими ребрами первого цвета. Несложно заметить, что получится именно то, что
нужно.


\sol  \smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.13}\\
\pic\label{1}
\end{tabular}
\end{center} %картинка

\sol  \smallskip
\begin{center}
\begin{tabular}{c}
\epsfig{figure=cispict.12}\\
\pic\label{1}
\end{tabular}
\end{center} %картинка

\sol   Доказательство повторяет доказательство задачи 17 прошлой части. Приведём набросок.
Для 2-графов утверждение очевидно. А если есть рёбра $\geqslant3$-ёх цветов, то наш $d$-граф можно
получить подстановкой $d$-графов в некоторый 2-граф, у которых меньше вершин. Для них утверждение
выполнено по предположению индукции. А для исходного тогда выполнено в силу того, что класс
$CIS$-графов очевидно замкнут относительно дополнения и точно замкнут относительно подстановки, а класс $CIS$-$d$-графов точно замкнут относительно подстановки.

\sol   Это следствие задач 23, 17, 6.

\sol \begin{lemma}
Если в $CIS$-$d$-графе объединить два цвета, то он останется $CIS$-$d$-графом.
\end{lemma}
\begin{proof} Рассмотрим максимальное множество $A$ вершин данного $d$-графа без рёбер первого и второго
цвета. Пусть $B$ и $C$ --- максимальные множества вершин соответственно без рёбер первого цвета и
без второго цвета, содержащие множество вершин $A$. Заметим, что пересечение множеств $B$ и $C$
--- это множество $A$, иначе множество $A$ можно было бы расширить. Пусть $A_3,A_4,\dots,A_d$ ---
максимальные множества вершин соответственно без рёбер 3-го, 4-го, ..., $d$-го цветов. Так как
данный граф является $CIS$-$d$-графом, то множества $B,C,A_3,A_4,\dots,A_d$ пересекаются по одной
вершине, а, значит, и множества $A,A_3,A_4,\dots,A_d$ пересекаются по одной вершине. Поэтому при
склейке первого и второго цветов граф остаётся $CIS$-$d$-графом.
\end{proof}
Докажем, что в нашем $CIS$-$d$-графе нет разноцветных треугольников со сторонами первого, второго
и третьего цвета. Все рёбра 4-го, 5-го, ..., $d$-го цветов перекрасим в третий цвет. По лемме
получим $CIS$-3-граф. По условию в полученном $CIS$-$3$-графе нет разноцветных треугольников.
Поэтому и в первоначальном не было со сторонами первого, второго и третьего цветов.

\setcounter{num}{26}

\sol
%\hyperref
a) Рассмотрим произвольную пару непересекающихся максимальной клики $C$ и независимого множества
$S$. Для произвольной вершины $v$ обозначим за $N(v)$ множество соседей вершины $v$ в $S$.
Рассмотрим три вершины клики $u,v,w$. Среди множеств $N(u)\cap N(v)$, $N(v)\cap N(w)$ и $N(w)\cap
N(u)$ одно содержится в объединении двух других, иначе, выбрав в каждом по вершине, не
принадлежащую остальным двум множествам вершин, получаем дополнение к 3-расчёске на выбранных трёх
вершинах и вершинах $u,v$ и $w$. Если, например, $N(u)\cap N(v)$ содержится в объединении двух
других, то $N(u)\cap N(v)=N(u)\cap N(v)\cap N(w)$.

Теперь выберем такие $u$ и $v$ в клике, что $N(u)\cap N(v)$ минимально, то есть не может строго содержать пересечение
каких-либо двух других множеств соседей в $S$ вершин клики. Докажем, что $N(u)$ и $N(v)$ не пересекаются. Действительно,
для любой другой вершины $w$ из сказанного выше по определению $u$ и $v$ следует, что пересечение множеств $N(u)$ и $N(v)$
совпадает с пересечением множеств $N(u)$,$N(v)$ и $N(w)$, то есть все вершины клики соединены с вершинами из
пересечения $N(u)$ и $N(v)$. В силу максимальности клики получаем, что $N(u)$ и $N(v)$ не пересекаются.

Зафиксируем $S$. В графе $G$ выберем такие соединённые вершины $u$ и $v$, что они не имеют общих соседей в $S$,
и объединение множеств $N(u)$ и $N(v)$ минимально, то есть не содержится в любом другом объединении непересекающихся
$N(u')$ и $N(v')$, где вершины $u'$ и $v'$ соединены.

\begin{lemma} Для любых вершин $x$ и $y$ из $S$, таких что $x$ --- сосед $u$, $y$ --- сосед $v$, и для
любой вершины $a$ такой, что вершины $x,u,v,y,a$ образуют $A$-граф, вершины $a$ и $u$ имеют общего
соседа в $S$ и вершины $a$ и $v$ имеют общего соседа в $S$.
\end{lemma}

\begin{proof} Обозначим за $C$ любую максимальную клику, которая содержит вершины $u$ и $v$. Она не
пересекает $S$, потому что $u$ и $v$ не имеют общих соседей в $S$. Пусть вершина $x$ из $N(u)$,
вершина $y$ из $N(v)$, и ${x,u,v,y,a}$ --- $A$-граф. Множество вершин $N(a)$ содержится в
объединении $N(u)$ и $N(v)$, потому что иначе ${u,v,a,x,y,b}$ --- 3-расчёска, где вершина $b$ из
$N(a)$, но не из $N(u)$ и не из $N(v)$. Другими словами, множество вершин $N(a)$ содержится в
объединении множеств $N(u)$ и $N(v)$.

Пусть $a$ не имеет общих соседей с $v$. Тогда объединение множеств $N(a)$ и $N(v)$ строго содержится в объединении
множеств $N(u)$ и $N(v)$, так как вершина $x$ не из $N(a)$. Противоречие с минимальностью объединения $N(u)$ и $N(v)$.
Значит, вершина $a$ имеет общих соседей и с вершиной $u$, и с вершиной $v$.
\end{proof}


Далее будем писать $U(a)$ и $V(a)$ --- множество общих соседей вершины $a$ с найденными вершинами $u$ и $v$ соответственно.
Множества $C$ и $S$ также предполагаются фиксированными.

Назовём вершину $a$ минимальной, если

\smallskip

1) вершина $a$ соединена с вершинами $u$ и $v$

2) для любой другой вершины $b$, соединённой с вершинами $u$ и $v$, $N(a)$ не может строго содержать $N(b)$

3) $N(a)$ не содержит ни $N(u)$, ни $N(v)$.

\noindent{\bf Замечание.} Для минимальной вершины объединение множеств $U(a)$ и $V(a)$ равно $N(a)$ (для этого не нужно второе условие).

\smallskip

{\bf Лемма 2.} Существуют две такие минимальные вершины $a$ и $a'$, что вершины $x,u,v,y,a$ и $x',u,v,y',a'$ образуют $A$-графы и
в $S$ есть две вершины $w$ и $w'$, такие что $w$ соединена с $a$, но не соединена с $a'$, а $w'$ наоборот.

{\bf Доказательство.} Возьмём вершину $x$ из $N(u)$, а вершину $y$ из $N(v)$. Вершины $x,u,v,y$ образуют $\Pi$-граф, поэтому
по условию есть вершина $a$ такая, что {x,u,v,y,a} --- $A$-граф. Вершину $a$ можно считать минимальной, потому что если $a'$
соединена с вершинами $u$ и $v$ и $N(a')$ содержится в $N(a)$, то вершины $x,u,v,y,a'$ тоже образуют $A$-граф. Возьмём вершину
$x'$ из $U(a)$ и вершину $y'$ из $V(a)$. По условию есть (минимальная) вершина $a'$ такая, что вершины $x',u,v,y',a'$
образуют $A$-граф. В $N(a)$ есть вершина ($x'$), которой нет в $N(a')$. Но $N(a')$ не может строго содержатся в $N(a)$ в силу
минимальности вершины $a$. Поэтому в $N(a')$ также есть вершина, которой нет в $N(a)$.


\noindent{\bf Утверждение 1.} Пусть даны две минимальные вершины $a$ и $b$, соединённые ребром. Тогда выполнено одно из условий:

1) $U(a)$ содержит $U(b)$ и $V(b)$ содержит $V(a)$, или $U(b)$ содержит $U(a)$ и $V(a)$ содержит $V(b)$

2) Множества $U(a)$ и $U(b)$ не пересекаются и в объединении дают $N(u)$, и множества $V(a)$ и $V(b)$ не пересекаются и в объединении дают $N(v)$

\noindent{\bf Доказательство.} Пусть множества $U(a)$ и $U(b)$ пересекаются и вершина $x$ принадлежит пересечению. Предположим,
что существуют вершины $y$ и $y`$ из $V(a)$ и $V(b)$ соответственно такие, что $y$ не из $V(b)$, и $y'$ не из $V(a)$ (это в точности
отрицание того, что одно из множеств $V(a)$ и $V(b)$ содержит другое). Тогда есть дополнение к 3-расчёске на вершинах $a,b,v,x',x,y$.
Противоречие. Значит, одно из множеств $V(a)$ и $V(b)$ содержит другое, и как следствие их пересечение не пусто согласно лемме 1.
А значит одно из множеств $U(a)$ и $U(b)$ содержит другое. В силу минимальности вершин $a$ и $b$, получаем первый случай.

Пусть множества $U(a)$ и $U(b)$ не пересекаются. Тогда в силу выше сказанного множества $V(a)$ и
$V(b)$ не пересекаются. А, значит, множества $N(a)$ и $N(b)$ не пересекаются. В силу выбора вершин
$u$ и $v$, объединение множеств $N(a)$ и $N(b)$ совпадает с объединением множеств $N(u)$ и $N(v)$,
что даёт второй случай.

\noindent{\bf Утверждение 2.} Пусть даны две минимальные вершины $a$ и $b$, не соединённые ребром. Тогда выполнено хотя бы одно из условий:

1) $U(a)$ содержит $U(b)$ и $V(b)$ содержит $V(a)$

2) $U(b)$ содержит $U(a)$ и $V(a)$ содержит $V(b)$

3) $U(a)=U(b)$ или $V(a)=V(b)$

\noindent{\bf Доказательство.} Пусть можно выбрать вершины $x$ и $y$ в $U(b)$ и $V(b)$ соответственно так, что $x$ и $y$ не
лежат в $N(a)$. Тогда имеем дополнение к 3-расчёске на вершинах $u,v,b,y,x,a$. Невозможность такого выбора означает выполнение
хотя бы одного из трёх условий.

\smallskip

1) Будем искать вершины минимальные $a$ и $b$, для которых выполнено третее условие утверждения 2, но $N(a)\neq N(b)$.

Сначала возьмём вершины $a$ и $b$ из леммы 2. Отметим, что для них выполнено $N(a)\neq N(b)$. Если они не искомые, рассмотрим
случай 2 в утверждении 1. Возьмём $x$ из $U(a)$ и $y$ из $V(b)$. И по условию найдём (минимальную) вершину $c$, такую что
${x,u,v,y,c}$ --- $A$-граф. Отметим, что $N(c)\neq N(a)$ и $N(c)\neq N(b)$. И если $N(a)$ и $N(c)$ не пересекаются, то
$N(c)=N(b)$ --- противоречие.

Значит, можно считать, что выполнено первое условие утверждения 2 и $N(a)\neq N(b)$. Либо вершины
искомые, либо можно выбрать вершины $x$ и $y$ такие, что $x$ из $U(a)$, но не из $U(b)$, а вершина
$y$ из $V(b)$, но не из $V(a)$. По условию есть (минимальная) вершина $c$, такая что ${x,u,v,y,c}$
--- $A$-граф. Если $U(a)=U(c)$ или $V(a)=V(c)$ или $U(b)=U(c)$ или $V(b)=V(c)$, то мы нашли
требуемые вершины, так как $N(a)\neq N(c)$ и $N(b)\neq N(c)$. Пусть нет. Если $V(c)$ не
пересекается с $V(b)$, то множества вершин $V(a)$ и $V(c)$ также не пересекаются и их объединение
не равно $N(v)$, так как $V(b)$ строго содержит $V(a)$. Имеем противоречие. Значит, для пары
вершин $c$ и $b$ возможен только случай 1 утверждения 1. Так как вершина $y$ принадлежит $V(b)$,
но не принадлежит $V(c)$, то возможен только случай 1 утверждения 2. Аналогично для пары вершин
$a$ и $c$. Заменим пару вершин $a$ и $b$ на пару вершин $a$ и $c$. Заметим, что мы вернулись к
прежнему случаю 1 утверждения 2, но $U(b)$ уменьшилось. Значит, после нескольких таких замен
получим искомую пару.

2) Заметим, что у полученной пары выполняется лишь случай 3 утверждения 2, то есть они не
соединены. Пусть $U(a)=U(b)$. Возьмём вершины $y$ и $y'$, такие что вершина $y$ из $V(a)$, но не
из $V(b)$, а вершина $y'$ из $V(b)$, но не из $V(a)$. Возьмём вершину $x$ из $U(a)=U(b)$. По
условию есть (минимальная, по замечанию) вершина $c$, такая что вершины $x,u,v,y,c$ образуют
$A$-граф. Вершины $c$ и $a$ соединены, иначе имеем дополнение к 3-расчёске на вершинах
$u,v,a,y,x,c$.

Для пары вершин $a$ и $c$ не выполняется случай 1 утверждения 1, потому что вершина $x$ из $U(a)$,
но не из $U(c)$, вершина $y$ из $V(a)$, но не из $V(c)$. Значит, выполняется случай 2 утверждения
1. И объединение непересекающихся $U(a)$ и $U(c)$ даёт $N(u)$. Аналогично с $V(a)$ и $V(c)$. Но
$U(a)=U(b)$ и $U(b)$ и $U(c)$ не пересекаются, поэтому возможны только случай 2 утверждения 1 и
случай 3 утверждения 2. Но в случае 2 утверждения 1 получаем $V(a)=V(b)$ --- противоречие. В
другом случае получаем, что $V(b)=V(c)$ и $V(b)$ и $V(a)$ не пересекаются. Автоматически получаем,
что $b$ и $c$ не соединены.

Аналогично получаем вершину $d$, которая соединена с $b$, не соединена с $a$, $U(d)=U(c)$ и
$V(d)=V(a)$. Для вершин $c$ и $d$ может выполняться только случай 3 утверждения 2, поэтому вершины
$c$ и $d$ не соединены. Возьмём произвольную вершину $x'$ из $U(d)=U(c)$. Вершины
$x,u,v,a,y,d,x',c,y',b$ образуют $G_{10}$.

\sol%28
Пусть фиксирована вершина $v$. Запись $u_1,u_2,u_3,w_1,w_2,w_3:$ a+ b- c+, где a,b и c ---
целые числа означает, что если вершина $v$ соединена с вершинами $v_a$ и $v_c$ и не соединена с
вершиной $v_b$, то тогда вершины $u_1,u_2,u_3,w_1,w_2,w_3$ образуют 3-расчёску (или
3-антирасчёску). Причём вершины $u_1,u_2,u_3$ образуют клику, вершины $w_1,w_2,w_3$ образуют
независимое множество вершин. В случае 3-расчёски вершины $u_i$ и $w_j$ соединены, если и только
если $i=j$. В случае 3-антирасчёски вершины $u_i$ и $w_j$ не соединены, если и только если $i=j$.
Если $u_1$ --- это $v_x$, то вместо $u_1$ будем писать $x$. В других случаях a+ будет означать,
что вершины $v$ и $v_a$ соединены, и a- --- наоборот.

a) Заметим, что в $G_{10}$ есть $\Pi$-подграфы, не дополненные до $A$-подграфов. Для каждого
такого $\Pi$-графа мы будем добавлять вершину, которая его дополняет до $A$-графа. Затем из того,
что нет 3-расчёсок и 3-антирасчёсок, можно будет выяснить какие рёбра между новой вершиной и
вершинами $G_{10}$, кроме одной, проведены, а какие нет.

{\bf $v'_7$}) $\Pi$-подграф 3 4 5 6 не содержится в $A$-подграфе графа $G_{10}$, значит, по
условию есть вершина $v$, для которой 3- 4+ 5+ 6-.

4 5 v 3 6 8: 8+ Поэтому вершины $v$ и $v_8$ не соединены, то есть 8-.

Пусть вершины $v$ и $v_1$ соединены, то есть 1+.

5 1 v 0 4 6: 1+ 0+  Значит, 0-.

9 1 v 8 6 4: 1+ 9+  Значит, 9-.

2 3 4 8 0 v: 2- 0-  Значит, 2+

1 2 9 8 0 v: 1+ 2+ 9- 0-  Противоречие. Итак, 1-.

1 5 9 3 v 8: 9-

1 5 9 v 0 6: 9+ 0-

2 9 v 0 4 8: 2+ 9+ 0+

Откуда следует, что 9+ 0+ 2-. То есть вершина $v$ ведёт себя противоположно вершине $v_7$. Все рёбра, кроме одного, определены.

{\bf $v'_6$})$\Pi$-подграф 7 8 9 5 не содержится в $A$-подграфе графа $G_{10}$, значит по условию
есть вершина $v$, для которой 7- 8+ 9+ 5-.

2 8 9 v 5 7: 2-. То есть 2+.

Пусть 1+.

1 2 v 8 0 5: 1+ 0+  Тогда 0-

8 9 v 7 0 4: 0- 4+  Тогда 4-

1 9 v 8 3 5: 1+ 3+  Тогда 3-

1 2 3 4 0 v: 1+ 3- 4- 0- Противоречие. Значит, 1-.

1 5 9 7 4 v: 4-

8 9 v 7 0 4: 4+ 0-

1 9 0 v 3 5: 0+ 3-

Последовательно получаем 4+ 0+ 3+. Значит, вершина $v$ ведёт себя противоположно вершине $v_6$.

{\bf Ребро $(v'_6,v'_7)$} Пусть нет, тогда 3 4 6$'$ 1 7$'$ 8

{\bf $v'_1$}Сделав перенумерацию $$(0,1,2,3,4,5,6,7,8,9)\rightarrow (0,1,2,9,8,7,6,5,4,3),$$ можно
считать, что мы нашли 5$'$ и 6$'$, соединённые ребром. $\Pi$-подграф 7 5$'$ 6$'$ 9 не содержится в
$A$-подграфе графа $G_{10}\cup v_6'\cup v_7'$, значит по условию есть вершина $v$, для которой 7-
5$'$+ 6$'$+ 9-.

5 6 8 7 9 v: 8-. Откуда 8+.

Пусть 2+.

2 8 v 5$'$ 4 9: 2+ 4+  Тогда 4-

3 5 6 v 7 4: 4- 3-  Тогда 3+

2 3 v 0 7 4: 2+ 4- 3+ 0+ Тогда 0-

6$'$ 8 v 0 7 5: 0- 5+ Тогда 5-

2 5 9 0 6$'$ v: 2+ 5- 0- Противоречие. Значит, 2-.

2 3 6$'$ v 9 7: 3+  Значит, 3-

3 5 6 v 7 4: 3- 4- Значит, 4+

5$'$ 0 v 7 9 4: 4+ 0+ Значит, 0-

5$'$ 8 v 3 9 v: 3- 6+ Значит, 6-

Вершина $v$ ведёт себя противоположно вершине $v_1$.

Граф $G_{10}$ допускает несколько перенумераций: $$(0,1,2,3,4,5,6,7,8,9)\rightarrow
(4,2,1,5,6,7,8,9,0,3)\rightarrow(4,2,1,3,0,9,8,7,6,5,4).$$ Так можно вершины 0, 4, 6, 8 можно
перевести друг в друга, вершины 3, 5, 7, 9 можно перевести друг в друга и вершины 1 и 2 также.
Вершину из каждой группы мы нашли, а значит, перенумеровав, получаем все остальные вершины.

{\bf b)} В следующих пунктах могут быть опущены слова: "Пусть нет, тогда".

{\bf Ребро $(v'_7,v'_9)$} 4 7$'$ 9$'$ 2 0 6

{\bf Ребро $(v'_6,v'_0)$)} 0$'$ 6$'$ 8 9 7 4

{\bf Ребро $(v'_6,v'_8)$)} 1 3 8$'$ 6$'$ 5 7

{\bf Ребро $(v'_6,v'_9)$)} 4 6$'$ 9$'$ 4 0 7

{\bf Ребро $(v'_5,v'_9)$)} 3 4 6$'$ 7$'$ 5$'$ 9$'$ по пунктам d), g) и j)

\noindent Тем самым, мы нашли все рёбра между вершинами 3$'$,4$'$,\dots,9$'$,0$'$.

{\bf Ребро (2$'$,4$'$)} 1 0 4$'$ 5 2$'$ 8

{\bf Ребро (2$'$,6$'$)} 3 4 6$'$ 7 5 2$'$

{\bf Ребро (2$'$,3$'$)} 3$'$ 5 6 8 4 2$'$

Используя найденные три ребра и перенумерацию получаем ребро (1$'$,2$'$): 6 7 0$'$ 2$'$ 3 1$'$

Итак, все рёбра найдены.

{\bf a)} Пусть вершины $v_2$ и $v_2'$ соединены ребром. Рассмотрим $\Pi$-граф 4 2 2$'$ 0. Он не
является подграфом $A$-подграфа $2G_{10}$, потому что нет вершины одновременно соединённой с
вершинами $v_2$ и $v_2'$. Тогда по условию в графе $G$ существует вершина $v$, для которой 4- 2+
2$'$+ 0-.

1) Сначала докажем, что 1-. Предположим противное и докажем, что вершина $v$ ведёт себя так же, как вершина 7.

Итак, 1+ 2+ 4- 0-.

1 2 3 4 0 v: 3-. Поэтому 3+.

2 3 v 8 0 6: 6+ 8-

1 3 v 6 4 8: 6- 8+

Откуда либо 6- 8-, либо 6+ 8+.

Пусть 6-. Тогда 8-.

1 2 5 4 6 v: 5- 6- Тогда 5+

1 2 9 8 0 v: 8- 9- Тогда 9+

5 9 v 6 8 3: 6- 8- 5+ 9+ Противоречие. Значит, 6+ и 8+.

2 5 v 6 8 4: 5+ Откуда 5-.

1 9 v 8 3 5: 9+ Откуда 9-.

Итак, вершина $v$ ведёт себя в $G_{10}$ так же, как вершина 7. Рассмотрим новый $G_{10}$, который
получен из старого заменой вершины $v_7$ на $v$.

Вершина 5$'$ соединена с 3 и 0 и не соединена с 4 и 9, следовательно согласно нахождению вершины
$v'_7$ в пункте $a)$ прошлой задачи, вершина 5$'$ не соединена с вершиной $v$ (выполняющей роль
вершины 7). Вершина 4$'$ соединена с 9 и 0 и не соединена с 3 и 5, следовательно согласно
нахождению вершины $v'_6$ в пункте $a)$ прошлой задачи, вершина 4$'$ не соединена с вершиной $v$
(выполняющей роль вершины 7). И наконец, вершина 2$'$ соединена с вершинами 4' и 5' (которые ведут
себя противоположно вершинам 4 и 5 в новом $G_{10}$) и не соединена с 3 и 9, следовательно
согласно нахождению вершины $v'_1$ в пункте $a)$ прошлой задачи, вершина 2$'$ не соединена с
вершиной $v$ (выполняющей роль вершины 7). Что противоречит предположению.

2) Значит, 1-.

Пусть 6+.

1 5 6 0 4 v: 6+ 5- Тогда 5+

2 9 v 4 0 6: 6+ 9+ Тогда 9-

2 5 v 6 8 4: 5+ 6+ 8+ Тогда 8-

2 5 9 3 6 v: 3+ 5+ 6+ 9- Тогда 3-

1 5 9 3 v 8: 3- 8- 9- 5+ Противоречие. Значит, 6-.

2 5 9 v 6 0: 5- 9-

1 5 9 v 0 6: 5+ 9+

Значит, либо 5+ 9-, либо 5- 9+.

1 3 7 v 6 0: 3+ 7+

2 3 7 v 0 6: 3- 7-

Значит, либо 3+ 7-, либо 3- 7+.

1 3 7 9 4 v: 3- 7+ 9-

1 5 9 7 4 v: 5- 7- 9+

Значит, либо 3+ 5+ 7- 9-, либо 3- 5- 7+ 9+.

3) Пусть 3- 5- 7+ 9+. Тогда вершина $v$ ведёт себя в графе $G_{10}$ также, как вершина 8.
Рассмотрим новый $G_{10}$, который получен из старого заменой вершины $v_8$ на $v$.


Вершина 5$'$ соединена с 3 и 0 и не соединена с 4 и 9, следовательно согласно нахождению вершины
$v'_7$ в пункте $a)$ прошлой задачи, вершина 5$'$ не соединена с вершиной $v$ (выполняющей роль
вершины 8). Вершина 4$'$ соединена с 9 и 0 и не соединена с 3 и 5, следовательно согласно
нахождению вершины $v'_6$ в пункте $a)$ прошлой задачи, вершина 4$'$ не соединена с вершиной $v$
(выполняющей роль вершины 8). И наконец, вершина 2$'$ соединена с вершинами 4' и 5' (которые ведут
себя противоположно вершинам 4 и 5 в новом $G_{10}$) и не соединена с 3 и 9, следовательно
согласно нахождению вершины $v'_1$ в пункте $a)$ прошлой задачи, вершина 2$'$ не соединена с
вершиной $v$ (выполняющей роль вершины 8). Что противоречит предположению.

4) Пусть 3+ 5+ 7- 9- 8-. Тогда вершина $v$ ведёт себя в графе $G_{10}$ также, как вершина 4.
Рассмотрим новый $G_{10}$, который получен из старого заменой вершины $v_4$ на $v$.

%Далее copy-paste

Вершина 9$'$ соединена с 7 и 6 и не соединена с 8 и 5, следовательно согласно нахождению вершины
$v'_7$ в пункте $a)$ прошлой задачи, вершина 9$'$ не соединена с вершиной $v$ (выполняющей роль
вершины 4). Вершина 8$'$ соединена с 5 и 6 и не соединена с 7 и 9, следовательно согласно
нахождению вершины $v'_6$ в пункте $a)$ прошлой задачи, вершина 4$'$ не соединена с вершиной $v$
(выполняющей роль вершины 4). И наконец, вершина 2$'$ соединена с вершинами 9' и 8' (которые ведут
себя противоположно вершинам 9 и 8 в новом $G_{10}$) и не соединена с 7 и 5, следовательно
согласно нахождению вершины $v'_1$ в пункте $a)$ прошлой задачи, вершина 2$'$ не соединена с
вершиной $v$ (выполняющей роль вершины 4). Что противоречит предположению.

5) Пусть 3+ 5+ 7- 9- 8+

1 5 9 7 v 6$'$: 6$'$-

v 6$'$ 8 5 0 7: 6$'$+

Что завершает доказательство.

{\bf b)} Если вершины 1 и 2 поменять местами с вершинами 1$'$ и 2$'$, то оба $G_{10}$ превратятся
в $P$. Осталось заметить, что вершины $x$ и $x'$ ведут себя противоположно в каждом из двух $P$.

{\bf c)} Так как в $2P$ вершины попарно не различимы, то есть для любых двух существует
перенумерация, переводящая одну во вторую, то в пункте a) мы фактически доказали, что если граф
$G$ с указанными свойствами содержит $2P=2G_{10}$ (пункт b)),то все неопределённые рёбра не
проведены.

Заметим, что дополнение к $2P$ --- это снова $2P$, но, может быть, другой. В каждом $P$ поменяем
местами внешний пятиугольник и внутреннюю звезду, затем поменяем местами внешние звёзды двух $P$.
Заметим, что все рёбра, кроме неопределённых, заменены на противоположные.

Рассмотрим дополнение к графу $G$. В нём снова все $\Pi$-подграфы содержатся в $A$-подграфах,
потому что $\Pi$-граф и $A$-граф самодополнительные. Он снова не содержит 3-расчёску и её
дополнение. И теперь он содержит $2P$, но все неопределённые рёбра у него проведены. Противоречие
с пунктом $a)$.





\end{document}
