\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{subcaption}
\usepackage{float}
\usepackage[a4paper,left=15mm,right=15mm,top=0mm,bottom=20mm]{geometry}
\usepackage{tikz}
\parindent=0mm
\parskip=3mm
\pagestyle{empty}

\title{Домашнее задание №8 \\
      \large Группа 504}
\date{}

\begin{document}

  \newcommand{\BCf}[2]{{{#1} \choose {#2}}}
  \newcommand{\BCCf}[2]{\ensuremath{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}}
  \newcommand{\diam}{\text{ diam}}
  \newcommand{\Aut}{\text{ Aut}}

 \maketitle
 
 \vspace{-20 pt}
 Количество баллов на зачёт: \textbf{8.5}
 \vspace{10 pt}
 \begin{enumerate}
  \item \textit{(1 балл)} Подсчитать количество гамильтоновых циклов в полном графе $K_n$, построенном на $n>2$ вершинах.  
  
  \item \textit{(1.5 балла)} Вывести формулу для подсчета общего количества простых циклов в полном графе $K_n$.  
  
  \item \textit{(0.5 балла)} Доказать, что любой турнир $T$ либо сильно связный, либо может быть превращен в таковой изменением ориентации только лишь одного ребра.   
  
  \item \textit{(1.5 балла)} Доказать, что любой сильно связный турнир $T$, построенный на $n$ вершинах, содержит циклы длины $3,4,\ldots,n$. 
	  Следствием этого утверждения является, в частности, тот факт, что в любом сильно связном турнире существует гамильтонов цикл.    
	  
  \item \textit{(1 балл)} Доказать, что среди $n>3$ вершин сильно связного турнира $T$ найдутся по крайней мере две вершины $x$, такие, что орграф $T-x$ остается сильно связным. 
  
  \item \textit{(2 балла)}  Доказать, что любой турнир имеет нечетное количество гамильтоновых путей.  
  
  \item \textit{(0.5 балла)} Доказать, что у $k$-связного графа, построенного на $n$ вершинах, количество $m$ ребер больше или равно $kn/2$.  
  
  \item \textit{(1.5 балла)} Пусть у нас задана тройка натуральных чисел $\kappa<\lambda<\delta$. 
	  Привести алгоритм построения графа $G$, у которого $\kappa(G) = \kappa$, $\lambda(G)= \lambda$, а $\delta(G) = \delta$.
	  
  \item \textit{(1.5 балла)} Пусть $G$ есть простой связный граф, в котором $\delta(G)\geq n-2$, где $n$ --- количество вершин в графе. 
	  Доказать, что в этом случае $\kappa(G)=\delta(G)$. Предъявить для любого $n>3$ граф с $\delta(G)=n-3$, у которого $\kappa(G)<\delta(G)$. 
	  
  \item \textit{(1.5 балла)} Пусть $G$ есть простой связный граф, построенный на $n$ вершинах, в котором $\deg(x)+\deg(y)\geq n-1$ для 
	  любой пары несмежных между собой вершин $x$ и $y$. Доказать, что в этом случае $\lambda(G)=\delta(G)$.  
	  
  \item \textit{(1.5 балла)} Пусть $G$ есть простой связный граф, в котором $\delta(G)\geq (n+k-2)/2$, где $n$ --- количество вершин в графе, 
		    $n\geq k+1$. Доказать, что в этом случае $G$ является $k$-связным графом, то есть что $\kappa(G)\geq k$.  
 \end{enumerate}

\end{document}
