Теорема о числе ребер в дереве

Пусть – дерево, , тогда .

Доказательство. Так как в дереве нет циклов, то . Дерево связный граф, следовательно, , тогда или .




double arrow
Сейчас читают про: