
\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{Домашняя работа 6.}{Эйлеровы и Гамильтоновы графы}
	\begin{task}{COMB}{70}
		(2 балла) Предположим, что мы удалили ребро $e = \{x, y\}$ в эйлеровом графе $G$.
		Доказать, что количество реберно не повторяющихся путей в графе $G' = G - e$, из $x$ в $y$,
		нечетно. Кроме того, показать, что среди всех этих путей количество путей, не являющихся простыми, четно.
	\end{task}
	\begin{solution}
	\end{solution}

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

	\begin{task}{COMB}{72}
		(1 балл). С использованием двух предыдущих упражнений доказать справедливость
		еще одной характеризации эйлерова графа: нетривиальный связный граф $G$ является
		эйлеровым тогда и только тогда, когда каждое его ребро $e$ принадлежит нечетному количеству циклов в $G$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{73}
		(2,5 балла) Возможно ли удалить в графе Петерсена ребра так, чтобы в полученном
		в результате удаления этих ребер графе $G$ существовал эйлеров цикл и $G$ был связен?
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{74}
		(2,5 балла) Обозначим через $h(D)$ количество гамильтоновых путей в простом орграфе $D$.
		Доказать, что для орграфа $D$ и орграфа $\bar{D}$, являющегося дополнением к $D$ до
		полного орграфа, построенного на $n$ вершинах (то есть орграфа, в котором любые две вершины
		соединены между собой парой разнонаправленных ребер), справедливо равенство $h(D) \equiv h(\bar{D}) \pmod{2}$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}