
\documentclass[12pt,fleqn,a4paper]{article}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{ntheorem}
\usepackage{tikz}
\usepackage{verbatim}

\usetikzlibrary{arrows,shapes}

\tikzstyle{vertex}=[circle,fill=black,minimum size=3pt,inner sep=0pt]
\tikzstyle{edge} = [draw,thick,-]

\newtheorem{definition}{Определение}
\newtheorem*{solution}{Решение}

\newenvironment{task}[2] {
	\noindent\fbox{\bf {#1} {#2}.}
}{
}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1} {#2}.
  \end{center}
}

\let\origenumerate\enumerate
\let\origendenumerate\endenumerate
\renewenvironment{enumerate}{\origenumerate[topsep = 0pt, noitemsep]}{\origendenumerate}

\begin{document}
	\mytitle{Домашняя работа 9.}{Связность}
	\begin{task}{COMB}{106}
		(1,5 балла) Доказать, что для любого $3$-регулярного простого графа $G$ реберная и вершиная связность совпадают.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{107}
		(1 балл) Доказать, что односвязный граф $G$ является реберно $k$-связным тогда и только тогда, когда любой блок $B_i$ такого графа реберно $k$-связный.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{108}
		(1,5 балла) Доказать, что граф $G$ является реберно двусвязным тогда и только тогда, когда его можно представить в виде
		$G = G_0 \cup G_1 \cup \dots \cup G_k$, где $G_0$ --- произвольный цикл в графе $G$, а $G_i$, i > 0, 
		представляет собой либо ручку, либо замкнутую ручку для подграфа $G_0 \cup G_1 \cup \dots \cup G_{i - 1}$ графа $G$.
	\end{task}
	\begin{solution}
	\end{solution}

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

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

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

	\begin{task}{COMB}{112}
		(1 балл). Доказать, что любой $k$-связный граф $G$, построенный на $n \ge 2k$ вершинах,
		$k \ge 2$, содержит цикл $C$, длина которого больше или равна $2k$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}