
\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{Домашняя работа 4.}{Основные понятия теории графов и их автоморфизмы}
	\begin{task}{COMB}{38}
		(1 балл) Доказать, что любой цикл наименьшей длины в графе $G$ представляет собой индуцированный подграф.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{39}
		(1,5 балла) Доказать, что любая вершина в простом связном графе $G$, построенном на $n \ge 3$ вершинах и отличном от $K_n$, 
		принадлежит некоторому индуцированному подграфу $P_3$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{40}
		(2 балла) Доказать, что любой граф $G$ без петель содержит остовный двудольный подграф $F$, 
		степень любой вершины $x$ в котором больше или равна $deg(x)/2$, где $deg(x)$ --- степень той же вершины в исходном графе.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{41}
		(2 балла) Пусть $G$ есть простой граф без треугольников, то есть граф, не содержащий $K_3$
		в качестве своего индуцированного цикла. Показать, что максимальное количество ребер
		в таком графе не превосходит $n^2/4$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{42}
		(1 балл) Граф $G$ называется самодополненным (self-complementary), если он изоморфен своему дополнению $\bar{G}$.
		Привести примеры самодополненных графов, построенных на четырех и пяти вершинах.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{43}
		(1 балл) Доказать, что для любого простого графа $G$ группа $Aut(G) = Aut(\bar{G})$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{44}
		(1.5 балла) Доказать, что порядок группы автоморфизмов любого турнира есть нечетное число.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}