Изменения

# Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.

# Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.

# Дан код Прюфера дерева. Найдите степень каждой вершины, не восстанавливая дерево явно.

# Даны числа $d_1, d_2, \ldots, d_n$. Докажите, что количество деревьев, в которых $deg(1) = d_1$, ..., $deg(n) = d_n$ равно $\frac {(n-2)!} {\Pi (d_i - 1)!}$

# Обобщение формулы Кэли. Пусть дан полный граф, и остовный лес в нём, компоненты связности леса состоят из $c_1, c_2, \ldots, c_k$ вершин. Докажите, что число способов добавить ребра, чтобы получилось остовное дерево, равно $c_1 c_2 \ldots c_k (c_1+c_2+\ldots+c_k)^{k-2}$.

# Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 -2$