Согласно теореме, в дереве с n вершинами количество рёбер равно n − 1. 13

Доказательство: нужно проводить рёбра по одному и следить за количеством несвязанных кусочков. 3 Изначально есть n вершин, никак не соединённых между собой. 3 При проведении первого ребра будут связаны две вершины. 3 Далее, как бы ни проводили новые рёбра, количество несвязанных кусочков будет уменьшаться на 1: ведь если провести ребро внутри связанного кусочка, образуется цикл. 3 В конце должен получиться один связанный кусочек — весь граф. 3

Пример: нужно определить, сколько рёбер в дереве, у которого 15 вершин. 2 Так как вершин у дерева на 1 больше, чем рёбер, значит, количество рёбер на 1 меньше количества вершин: 15 − 1 = 14 рёбер. 2