Лемма. В дереве, где не меньше двух вершин, есть лист (вершина степени 1). Возьмём самую длинную цепь в дереве \( v_1 v_2 \ldots v_k \) и её конец \( v_k \). Если бы из \( v_k \) выходило ещё одно ребро \( v_k w \), то либо \( w \) — новая вершина, и цепь можно удлинить (противоречие с максимальностью), либо \( w = v_i \) — вершина цепи, и \( v_i \ldots v_k v_i \) — цикл (противоречие с тем, что граф — дерево). Значит, степень \( v_k \) равна 1.
Индукция по числу вершин. Дерево из одной вершины имеет 0 рёбер: формула верна. Пусть формула верна для всех деревьев с \( n - 1 \) вершинами, и дано дерево \( T \) с \( n \ge 2 \) вершинами. По лемме в \( T \) есть лист \( v \). Удалим \( v \) вместе с единственным его ребром: граф останется связным (через вершину степени 1 не проходит ни одна цепь между другими вершинами) и без циклов, то есть будет деревом с \( n - 1 \) вершинами, а значит, по предположению, с \( n - 2 \) рёбрами. Тогда в \( T \) рёбер \( (n - 2) + 1 = n - 1 \), что и требовалось доказать.