
\documentclass[12pt,fleqn,a4paper]{article}

\usepackage[russian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumitem}
\usepackage{ntheorem}
\usepackage{tikz}
\usepackage{verbatim}

\sloppy

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

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

	\begin{task}{COMB}{83}
		(2 балла) Пусть $G$ есть простой граф на $10$ вершинах и $26$ ребрах. Доказать, что такой
		граф содержит в качестве своих индуцированных подграфов по меньшей мере пять 
		треугольников
	\end{task}
	\begin{solution}
	\end{solution}

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

	\begin{task}{COMB}{85}
		(2 балла) Доказать, что самодополненный граф $G$, построенный на $n$ вершинах, 
		существует тогда и только тогда, когда $n$ или $n - 1$ делится на $4$
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{86}
		(1 балл) Подсчитать количество автоморфизмов графов $P_n$, $C_n$ и $K_{n,m}$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}