\documentclass[12pt]{article}
\usepackage[left=1.5cm,right=1.5cm,top=1.5cm,bottom=1cm,bindingoffset=0cm]{geometry}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{euscript}
\usepackage{graphicx}
\usepackage{amsthm, amsmath, amssymb}
%\usepackage[text={163mm,255mm},centering]{geometry}
\usepackage{hyperref}
\newtheorem{thm}{Теорема}
\newtheorem*{lemma}{Лемма}
\newtheorem{sled}{Следствие}
\newtheorem{example}{Пример}
\newtheorem{utv}{Утверждение}
\theoremstyle{definition}
\newtheorem{opr}{Определение}
\theoremstyle{remark}
\newtheorem{zam}{Замечания}
\DeclareMathOperator\LIP{LIP}
\DeclareMathOperator\KR{KR}
\DeclareMathOperator\sign{sign}
\DeclareMathOperator\ROOT{Root}
\def\odin{\mathbf{1}}
\let\leq\leqslant
\let\geq\geqslant

\pagenumbering{gobble}

\begin{document}

\begin{center}

    \huge {Домашнее задание \textnumero 9}
		
		\large Группа 504

\end{center}    

\vspace{0.5cm}

Количество баллов на зачёт: \textbf{8,5}.

\begin{enumerate}

\item (0,5) Выразить количество остовных деревьев односвязного графа $G$ через количество остовных деревьев в каждом из $k$   блоков $B_1,\ldots,B_k$ графа $G$.

\item (1) Доказать, что вершинно односвязный граф $G$ является реберно $k$-связным тогда и только тогда, когда любой блок $B_i$ такого графа реберно $k$-связный.

\item (1,5) Граф называется кактусом, если каждый его блок представляет собой либо одиночное ребро, либо единственный цикл. В частности, любое дерево является кактусом. Предъявить кактусы, построенные на $2k+1$ и $2k$ вершинах соответственно и имеющие максимальное количество ребер. Доказать, что кактусы с большим количеством ребер при фиксированном $k$ построить невозможно.

\item (1) Описать разложение на ручки для графа Петерсена.

\item (1,5) Чему равно минимальное количество ручек в разложении графа, показанного на рисунке? Начальный цикл в разложении ручкой не считается.

\begin{center}
\includegraphics[height=3cm]{i15}
\end{center}


\item (1) Доказать, что простой граф $G$, построенный на трёх или более вершинах, двусвязен тогда и только тогда, когда для любой тройки различных вершин $(x, y, z)$ в $G$ есть простой путь из $x$ в $z$, проходящий через $y$. 

\item (0,5) Пусть $G$ есть вершинно двусвязный граф, и пусть вершины $x$ и $y$ этого графа соединены в $G$ путем $P$. Доказать или опровергнуть следующее утверждение: в графе $G$ найдется путь $Q$, соединяющий $x$ и $y$ и не пересекающийся с $P$ ни в каких внутренних вершинах этого пути.

\item (1) Пусть $D$ есть орграф, построенный на множестве вершин $[12]=\{1,2,\ldots,12\}$, в котором из $i$ в $j$ проведено ребро тогда и только тогда, когда $i$ делит $j$. Определить $\kappa(1,12)$ и $\lambda(1,12)$ в таком графе.

\item (1) Пусть $G$ вершинно $k$-связен. Образуем из $G$ новый граф $G'$ путём добавления к $G$ новой вершины $y$ и не менее $k$ рёбер из $y$ в $k$ различных вершин графа $G$. Доказать, что $G'$ также $k$-связен.

\begin{lemma}
Назовем $k$-веером из вершины $x$ в множество $Y$ набор из $k$ путей, начинающихся в $x$, заканчивающихся в $Y$, и не имеющих никаких общих вершин, кроме вершины $x$. Пусть $G$ есть $k$-связный граф, $x$ --- некоторая его вершина, а $Y$ --- набор из не менее чем $k$ вершин графа $G$, не включающий $x$. Доказать, что тогда существует $k$-веер из $x$ в $Y$.
\end{lemma}

\begin{proof}
Добавим в граф $G$ вершину $y$ и соединим её со всеми вершинами множества $Y$, образововав тем самым граф $G'$. Пользуясь результатом предыдущего упражнения, заключаем, что $G'$ $k$-связен. По теореме Менгера в $G'$ есть $k$ непересекающихся путей из $x$ в $y$. Удалив для каждого из этих путей замыкающую вершину $y$ вместе с инцидентным ей ребром, мы получим в графе $G$ $k$-веер из $x$ в $Y$.
\end{proof}

\item (1,5) Доказать, что в $k$-связном графе для любых $k$ вершин найдется цикл $C$, на котором лежат все эти $k$ вершин.

\item (1,5) Показать, что в условиях предыдущего упражнения мы не можем заранее задать порядок, в котором должны проходиться вершины, лежащие на общем для них цикле $C$.

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

\end{enumerate}

\end{document}