.03 Графы. Деревья.

На самом деле, это уже будет верно.

Допустим, что - связный, в нем вершин, рёбер и выполняется соотношение

но он - не дерево.

Но тогда, раз - связный, то у него всегда существует остовное дерево . Причем в будет ребер точно меньше, чем в , потому что иначе бы сам был бы своим остовным деревом, а это не так по предположению.

Следовательно, в ребер меньше, чем в , а вершин - столько же (по определению остовного дерева).

Но тогда получается, что раз для выполнялось соотношение

а в у нас ребер меньше , а вершин - столько же, т.е.

то для соотношение

уже выполняться не будет.

Противоречие, ведь - остовное дерево, в частности, просто дерево. А для дерева такое соотношение, как мы уже доказали, всегда выполняется.

Следовательно, сам должен был быть своим остовным деревом, то есть - это дерево и мы получаем, что формула

является критерием деревьев в классе связных графов.