\documentclass[12pt]{article}
\usepackage[left=1.5cm,right=1.5cm,top=1.5cm,bottom=1cm,bindingoffset=0cm]{geometry}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{euscript}
\usepackage{graphicx}
\usepackage{amsthm, amsmath, amssymb}
%\usepackage[text={163mm,255mm},centering]{geometry}
\usepackage{hyperref}
\newtheorem{thm}{Теорема}
\newtheorem{lemma}{Лемма}
\newtheorem{sled}{Следствие}
\newtheorem{example}{Пример}
\newtheorem{utv}{Утверждение}
\theoremstyle{definition}
\newtheorem{opr}{Определение}
\theoremstyle{remark}
\newtheorem{zam}{Замечания}
\DeclareMathOperator\LIP{LIP}
\DeclareMathOperator\KR{KR}
\DeclareMathOperator\sign{sign}
\DeclareMathOperator\ROOT{Root}
\def\odin{\mathbf{1}}
\let\leq\leqslant
\let\geq\geqslant

\pagenumbering{gobble}

\begin{document}

\begin{center}

    \huge {Домашнее задание \textnumero 6}
		
		\large Группа 504

\end{center}    

\vspace{0.5cm}

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

\begin{enumerate}

\item (1) Доказать, что в любом дереве $T$, максимальная степень $\Delta(T)$ вершины в котором равна $k$, существует по меньшей мере $k$ листьев. В каком дереве с таким условием существует ровно $k$ листьев?

\item (1,5) Полным $m$-арным деревом называется корневое дерево, у которого любая вершина, отличная от листа, имеет ровно $m$ сыновей. Предположим, что у такого дерева имеется $k$ вершин, отличных от листа. Доказать, что в таком дереве имеется $(m-1)k+1$ лист.

\item (1,5) Пусть $G$ есть простой граф с $\delta(G)\geq k$, а $T$ есть произвольное дерево с $k$ ребрами. Доказать, что в $G$ имеется подграф, изоморфный $T$.    

\item (2) Доказать следующее необходимое условие существования $k$ попарно реберно непересекающихся остовных деревьев в графе $G$: для любого разбиения множества $V(G)$ вершин графа $G$ на $r$ блоков, $r\in[2,|V(G)|]$, найдется по меньшей мере $k(r-1)$ ребер графа $G$, концы которых лежат в различных блоках разбиения.  

\item (2) {\small Пусть у нас имеется какое-то множество $G$, а также некоторый набор $H_1,\ldots,H_k$ его подмножеств. Говорят, что набор таких подмножеств обладает свойством Хелли (Helly property), если из того, что любая пара таких подмножеств имеет непустое пересечение, следует, что пересечение всех этих подмножеств не пусто. Так, если у нас имеется набор попарно пересекающихся интервалов на прямой, то их пересечение непусто.}

Доказать, что поддеревья любого дерева обладают свойством Хелли.

Иными словами, доказать, что для любого набора $T_1,\ldots,T_k$ поддеревьев дерева $T$, любые два их которых имеют непустое пересечение, найдется общая для всех этих поддеревьев вершина $x$.

Показать, что в случае связного графа, деревом не являющегося, это свойство может и не выполняться (указание: рассмотреть цикл $C_n$). 



\item (0,5) Построить деревья, отвечающие последовательностям Кэли 
$$
(1,2,3,4)\qquad \qquad\text{и}\qquad\qquad (3,3,3,3).
$$ 

\item (1,5) Какую степень имеет вершина с номером $k$ в дереве с последовательностью Кэли $(c_1,\ldots,c_{n-2})$?

\item (1,5) С помощью последовательностей Кэли подсчитать количество деревьев, имеющих в точности $k$ листьев, выразив это количество через числа Стирлинга $S(\cdot,\cdot)$ второго рода.

\item (1) Доказать, что количество корневых лесов, построенных на $n$ вершинах, описывается формулой $(n+1)^{(n-1)}$. 

\item (1,5) Дать комбинаторное доказательство следующего рекуррентного соотношения для числа $t_n$ деревьев, построенных на $n$ вершинах:
\begin{equation}
\label{eq:req_Cayley_1}
t_n=\dfrac{1}{2(n-1)}\sum\limits_{k=1}^{n-1}\dfrac{n!}{(k-1)!\,(n-k-1)!}\,t_k\,t_{n-k}.
\end{equation}



\end{enumerate}

\end{document}