Вот доказательство.
Теорема: пусть T будет любым деревом с i листьями. (|T|-i)/2 соответствует T.
Доказательство: по индукции. Если T - это дерево с i листьями, пусть T' будет деревом, которое получается при удалении всех листьев из T. T' имеет j <= i листьев. Аналогично, пусть T'' будет деревом, которое получается при удалении всех листьев из T'. T'' имеет k <= j листьев.
Примените теорему по индукции к T'', так что существует совпадение размера (|T''|-k)/2 = (|T|-i-j-k)/2 в T''. Набор ребер T-T' содержит по крайней мере j ребер, которые не попадают ни в один из ребер в T'' или друг в друга (выберите один инцидент для каждого листа в T'), поэтому добавьте эти ребра, чтобы сделать совпадение в T размера (|T|-i+j-k)/2. Поскольку j >= k, это как минимум (|T|-i)/2 ребер. QED.
Я скрыл проблемы пола / потолка с / 2, но я подозреваю, что доказательство будет работать, если вы их включите.