
\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{Домашняя работа 8.}{Связность}
	\begin{task}{COMB}{92}
		(2 балла). Построить наименьший $3$-регулярный граф $G$, 
		для которого $\kappa(G) = 1$. Доказать, что построенный граф
		действительно является минимальным.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{93}
		(2 балла) Возьмем четное количество $n$ вершин и расставим их равномерно по кругу.
		Зафиксируем некоторое четное натуральное число $k < n$ и проведем из любой вершины $k$ ребер,
		соединив эту вершину с $k/2$ вершинами слева по кругу от нее и с $k/2$ вершинами справа по кругу от нее.
		В результате получим $k$-регулярный граф, построенный на $n$ вершинах. Доказать, что для такого графа $\kappa(G) = k$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{94}
		(1,5 балла) Пусть $G$ есть простой связный граф, в котором $\delta(G)  \ge (n + k - 2)/2$, 
		где $n$ - количество вершин в графе, $n \ge k + 1$. 
		Доказать, что в этом случае $G$ является $k$-связным графом, то есть что $\kappa(G) \ge k$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{95}
		(1,5 балла) Пусть $G$ есть произвольный простой граф,
		$S$ - произвольное собственное подмножество множества $V(G)$ вершин этого графа.
		Показать, что в случае $|\partial(S)| < \delta(G)$ мощность $|S|$ подмножества $S$
		строго больше $\delta(G)$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{96}
		(2,5 балла) Пусть $G$ есть простой связный граф, диаметр которого равен двум,
		а $[S, \bar{S}]$ ($|S| \le |\bar{S}|$) --- это  минимальный реберный разрез (по чсилу ребер) в этом графе.
		Доказать, что любая вершина $x \in S$ имеет хотя бы одну смежную с ней вершину $y \in \bar{S}$.
		Используя этот факт, показать, что в таком графе $\lambda(G) = \delta(G)$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{97}
		(1 балл) Пусть у нас задана тройка натуральных чисел $\kappa < \lambda < \delta$.
		Привести алгоритм построения графа $G$, у которого $\kappa(G) = \kappa$, $\lambda(G) = \lambda$, а $\delta(G) = \delta$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}