
\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{Домашняя работа 11.}{Паросочетания}
	\begin{task}{COMB}{132}
		(1 балл) Определить числа $\alpha(G)$, $\alpha'(G)$, $\beta(G)$ и $\beta'(G)$ для графа $G = K_{n,m}$, $n \le m$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{133}
		(2 балла) Доказать, что для любого графа G справедливо неравенство $\alpha(G) > \sum\limits_{x \in V(G)} \frac{1}{\mathrm{deg}(x) + 1}$.
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{134}
		(2 балла) Показать, что для любого двудольного графа $G$ произведение 
		$\alpha(G) \cdot \beta(G) \ge |E(G)|$, причем равенство имеет место тогда и только тогда, когда граф $G$ является полным
		двудольным графом
	\end{task}
	\begin{solution}
	\end{solution}

	\begin{task}{COMB}{135}
		(2 балла) Доказать, что для любого простого графа $G$ с $|V(G)| = n > 2 \delta(G)$, 
		справедливо неравенство $\alpha'(G) \ge \delta(G)$.
	\end{task}
	\begin{solution}
	\end{solution}

\end{document}