\documentclass[14pt]{article}
\usepackage{graphicx}
\graphicspath{ {images/} }
\usepackage{caption}
\usepackage[utf8]{inputenc}
\usepackage{amsthm,amssymb, amsmath, amsfonts, amscd}
\usepackage[russian]{babel}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}
\begin{document}

\title{20 ноября 2017}
\date{}
\maketitle
\vspace{-35pt}

Количество баллов на зачет: \textit{8}

\begin{enumerate}

%\textit{(1.5 балла)} 


\item \textit{(1.5 балла)}  Найти максимальные паросочетания в графах $G_1$ и $G_2$, изображенных на рис.1, и доказать с помощью формулы Татта-Бержа, что найденные паросочетания действительно являются максимальными. 

\item \textit{(1.5 балла)}  Найти максимальное паросочетание в графе $G$, изображенном на рис.2, и доказать с помощью формулы Татта-Бержа, что найденное паросочетание действительно является максимальными.

\item \textit{(1.5 балла)} Показать, что в кубе $Q_k$ найдется по меньшей мере $2^{2^{k-2}}$ совершенных паросочетаний для всех $k\geq 2$.

\item \textit{(1 балл)} Назовем граф $G$ фактор-критическим,  \index{граф!- фактор-критический}  если в нем нет совершенного паросочетания, но при удалении любой вершины оно появляется. Доказать, что никакой двудольный граф $G[X,Y]$ фактор-критическим быть не может.

\item \textit{(1.5 балла)} Обозначим через $G_n$ граф, построенный на $2n$ вершинах $x_1,\ldots,x_n$ и $y_1,\ldots,y_n$, и имеющий ребра вида $\{x_i,x_{i+1}\}$, $\{y_i,y_{i+1}\}$, а также $\{x_i,y_i\}$. Подсчитать количество совершенных паросочетаний в таком графе.


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

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

\item \textit{(1.5 балла)} Пусть $G[X,Y]$ есть двудольный граф. Образуем из него граф $\tilde{G}$ добавлением к $Y$ дополнительной вершины $z$ в случае, если $n=|V(G)|$ есть нечетное число, а также добавлением к $Y$ ребер до превращения его в клику. Доказать, что исходный граф $G$ имеет паросочетание размером $|X|$ тогда и только тогда, когда в $\tilde{G}$ существует совершенное паросочетание.   

\item \textit{(1.5 балла)} Доказать, что любой кубический граф, имеющий не более двух мостов, допускает декомпозицию на пути длины $3$. 

\item \textit{(2 балла)} Для любого $k>1$ предъявить  $k$-регулярный граф, в котором совершенное паросочетание отсутствует. 

\begin{figure}[h]
\center{
\includegraphics[scale=0.4]{5_13_1}\caption{}
}
\end{figure}
\begin{figure}[h]
\center{
\includegraphics[scale=0.4]{5_13_2}\caption{}
}
\end{figure}

%\begin{figure}[h]
%\center{
%\begin{minipage}{0.4\linewidth}
%\center{
%\includegraphics[scale=0.1]{5_10_3}\caption{}
%}
%\end{minipage}
%\begin{minipage}{0.6\linewidth}
%\center{
%\includegraphics[scale=0.2]{5_10_4}\caption{} 
%}
%\end{minipage}
%}
%\end{figure}

\end{enumerate}
\end{document}