Верно ли, что в дереве можно любую вершину принять за корень, и количество листьев при этом изменится не более чем на 1?

Предыдущий
вопрос Следующий
вопрос

Да, верно. В любом дереве можно выбрать любую вершину в качестве корня, и количество листьев изменится не более чем на 1.

Листья — это вершины, у которых только одна связь (т.е. они соединены с одной другой вершиной). Когда вы выбираете новую вершину в качестве корня, то она становится соединенной с вершинами, которые были листьями относительно прежнего корня.

Если новая корневая вершина до этого была листом, то она потеряет статус листа, а вершина, с которой она была связана (и которая теперь станет её дочерней), может стать листом только в том случае, если у неё не останется других соединений.

Таким образом, максимум одно изменится в количестве листьев при выборе новой корневой вершины.