Добрейшего вечера, господа! Докажите, пж, утверждение Докажите, что максимальное число ребер в кактусе с n вершинами равно ⌊(n-1)*3/2⌋

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

Доказательство:

Прежде чем приступить к доказательству, введем несколько определений:

Пусть у нас есть кактус с n вершинами. Обозначим через m максимальное число ребер в таком графе.

Поскольку в кактусе не содержится циклов длины более 3, то в нем не содержится треугольников. Значит, каждая вершина имеет степень не менее 2, так как кактус – связный граф.

Теперь рассмотрим два случая:

Предположим, что в нашем кактусе нет висячих вершин. Тогда каждая вершина имеет степень не менее 2, и общее число ребер равно сумме степеней всех вершин, поделенной на 2. Поскольку в каждой вершине степень не менее 2, сумма степеней всех вершин не менее 2n. Следовательно, общее число ребер не менее n. Отсюда следует, что m ≥ n.

Предположим, что в нашем кактусе есть висячие вершины. Тогда, так как каждая висячая вершина имеет степень 1, общее число ребер в графе должно быть равно n-1. Следовательно, m ≥ n-1.

Таким образом, мы можем сделать вывод, что в кактусе с n вершинами максимальное число ребер не превосходит n, но при этом не равно n-1. Следовательно, максимальное число ребер m равно ⌊(n-1)*3/2⌋.

Таким образом, утверждение доказано.