Дерево есть связный подграф без циклов.
Индукцией по числу вершин можно показать, что (p,q) дерево имеет q = p-1 рёбер.
Теорема Кэли: Число помеченных деревьев (tp) с p вершинами равно: р^р-2, то есть t_p = p^p-2.

Доказательство Прюфера: Пусть Т – помеченное дерево с р вершинами. V = {1,2,…,p}. Сопоставим дереву Т единственный набор (а₁,… ,а_р-2) из V^p-2 следующим образом: выберем в Т висячую вершину v с наименьшей пометкой а₁. Аналогично найдём наименьшую пометку а₂ для висячей вершины в дереве Т-v (Т без v и без принадлежащих v ребер). И так далее… Остается одно ребро из Т. Набор А=(а₁,…,а_р-2) построен для дерева Т. Так как каждое a_i было единственно, то набор а единственный. Так как каждое помеченное дерево с р вершинами связано с единственным набором длины (р-2) из р элементов и так как число таких наборов равно р^р-2, то число помеченных деревьев t_p ≤ p^p-2. Продолжим Доказательство теоремы следующим утверждением.

Утверждение: Каждому набору длины (р-2) из 1,2,…,р можно единственным образом сопоставить помеченное дерево с р вершинами 1,2,…,р

Доказательство: Индукция по р.
Базис: р=2. V = {1,2}. p^p-2 = 2^2-2 = 2⁰ = 1. Набор а пуст. Для пустого набора существует только одно помеченное дерево.
Предположение индукции: предположим, что каждому набору длины (р-3) из 1,2,….,р-1 можно единственным образом сопоставить помеченное дерево с (р-1) вершинами 1,2,…,р-1.
Шаг: Пусть а={а1,а2,…,а(p-2)} длины (р-2) составлен из элементов 1,2,…,р. Пусть b₁ есть наименьшее натуральное число не из набора a и пусть с={c₂,…,c_p-2} есть набор длины (р-3), полученный из а уменьшением всех его координат, больших чем b₁, на единицу, тогда набор с состоит из чисел, принадлежащих множеству V_P-1={1,2,…,p-1}. Так как набор с состоит из (р-3) элементов, то по предположению индукции набору с соответствует единственное помеченное дерево Т_р-1 с (р-1) вершинами из V_p-1. Прибавим в дерево Т_р-1 по единице к каждой пометке вершины, превосходящей (b₁-1), затем введём вершину р с пометкой b₁ и соединим её с вершиной, помеченной числом а₁ в дереве Т_р-1. Однозначно получено дерево с р вершинами, соответствующее набору а. чтд.

Продолжим доказательство теоремы Кэли. Так как каждому из р^р-2 наборов длины (р-2) однозначно соответствует помеченное дерево с р вершинами, то t_p ≥ p^p-2. Получили: t_p ≤ p^p-2 и t_p ≥ p^p-2, следовательно t_p = p^p-2. чтд.

Комментарии запрещены.