\documentclass[a4paper, 12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\linespread{1.2}

\usepackage{amsthm,amssymb, amsmath, amsfonts, amscd}
\usepackage{texdraw}

\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}


\def\geq{\geqslant}
\def\leq{\leqslant}
\def\iff{\Leftrightarrow}
\def\therefore{\Rightarrow}
\def\because{\Leftarrow}

\newcommand{\mytitle}[2] {
  \begin{center}
      \bf {#1}. {#2}.
  \end{center}
}

\newenvironment{solution} {

{\it Решение.}
} {
}




\begin{document}

\mytitle{Домашнее задание 7}{Основные понятия теории графов. Деревья}
\begin{center}
      {Группа 102/3}
\end{center}

\begin{enumerate}

\item (1 балл) 
Пусть $G$ есть простой граф, степень любой вершины которого больше или равна $\delta$. Доказать, что в графе $G$ существует путь длины, большей или равной $\delta$. Для любого $k\geq 2$ предъявить простой граф $G$ с $\delta=k$, который не содержит путей, длина которых больше чем $k$.

\begin{solution}
\end{solution}

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

\item (1 балл) Пусть в простом графе $G$ с диаметром $2$ имеется точка сочленения. Доказать, что в графе $\bar{G}$ найдется изолированная вершина.

\begin{solution}
\end{solution}

\item (2 балла) Доказать, что любой $3$-регулярный граф $G$ имеет точку сочленения тогда и только тогда, когда в нем содержится мост.

\begin{solution}
\end{solution}

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

\begin{solution}
\end{solution}

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

\begin{solution}
\end{solution}

\item (1 балл) Графовая последовательность дерева $T$ имеет вид $5,4,3,2,1,\ldots,1$. Сколько единиц имеется в этой последовательности? 

\begin{solution}
\end{solution}

\item (1 балл) Подсчитать количество неизоморфных друг другу деревьев на $n\geq 2$ вершинах, диаметр которых меньше или равен трем.  

\begin{solution}
\end{solution}

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

\begin{solution}
\end{solution}

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

\begin{solution}
\end{solution}

\end{enumerate}

\end{document}


