Теорема названа в честь Артура Кэли, который доказал её в 1889 году.[1]
Сам Кэли признавал, что то же утверждение было доказано раньше Карлом Борхардом и в эквивалентной формулировке ещё раньше в статье Джеймса Джозефа Сильвестра 1857 года.[2]
В своей статье Кэли по сути доказывает более общее утверждение. Если раскрыть скобки выражения
то коэффициент при одночлене вида будет равен числу деревьев, у которых степени вершин равны степеням переменных данного терма: .
Кэли подробно разбирает случай и заявляет, что доказательство легко обобщается.
- Формула Кэли немедленно следует из свойств кода Прюфера — способа однозначного кодирования -вершинного помеченного дерева упорядоченной последовательностью из номеров его вершин.
- Одно из доказательств строится на следующем соотношении
- на экспоненциальную производящую функцию
- где обозначает число корневых деревьев на данных вершинах. По теореме Лагранжа об обращении рядов, из этого соотношения следует, что . Последнее влечёт формулу Кэли поскольку для каждого остовного дерева есть ровно способов выбрать корневую вершину.[3]
- Количество способов связывания графа, состоящего из несвязных компонент, каждая размером вершин, равно
- Здесь — общее количество вершин графа.
- Если каждая компонента состоит из одной вершины , то , и формула дает исходное число Кэли .
Biggs N. L., Lloyd E. K., Wilson R. J. Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.
Харари Ф., Палмер Э. Перечисление графов. — Мир, 1977.
David Benko, «A New Approach to Hilbert's Third Problem» The American Mathematical Monthly Vol. 114, No. 8 (Oct., 2007), pp. 665--676