Существует несколько способов доказать, что связный граф с ( n ) вершинами и ( n-1 ) ребром является деревом. Мы рассмотрим два из них: индукцией и с использованием свойств деревьев.

Доказательство 1: По индукции

База индукции: Для ( n = 1 ) граф состоит из одной вершины и не содержит рёбер. Это действительно является деревом (по определению, дерево - связный граф без циклов).

Индукция: Предположим, что утверждение верно для графов с ( k ) вершинами (графы с ( k ) вершинами и ( k-1 ) рёбер - деревья). Теперь рассмотрим граф с ( k + 1 ) вершинами и ( k ) рёбрами, который, согласно условию, тоже является связным.

Поскольку граф связный, мы можем выбрать любую вершину ( v ) и удалить одно из рёбер ( e ), инцидентное этой вершине. После удаления рёбра, граф останется связным (по определению связного графа, при удалении рёбер нельзя разъединить граф) до тех пор, пока не будет удалена вершина, соединенная с удаляемым рёбером.

Удалив это ребро, у нас останется граф с ( k ) вершинами и ( k - 1 ) рёбер. По предположению индукции, этот граф является деревом, то есть он связный и не содержит циклов.

Теперь возвращаем удалённое ребро ( e ) обратно в граф. Мы знаем, что добавление ребра к дереву создаст цикл. Таким образом, добавление ребра не нарушает свойство связности, но дает цикл, что делает граф не деревом.

Таким образом, граф с ( k + 1 ) вершинами и ( k ) рёбрами также будет являться деревом.

Доказательство 2: Свойства деревьев

Дерево по определению — это связный граф, который не содержит циклов, и которое удовлетворяет следующим свойствам:

Свойство связности: Дерево должно быть связным.Свойство количества рёбер: В дереве с ( n ) вершинами обязательно ( n - 1 ) рёбер.

Если мы имеем граф с ( n ) вершинами и ( n - 1 ) рёбер:

Граф связный: По условию задачи граф уже связан.

Отсутствие циклов: Предположим, что в нашем графе есть цикл. В таком случае, если мы удалим одно из рёбер этого цикла, граф останется связанным, и количество рёбер станет ( n - 2 ), что нарушает требование, что граф должен иметь ( n - 1 ) рёбер, чтобы быть деревом.

Таким образом, зная, что граф связный и с ( n - 1 ) рёбрами, мы можем утверждать, что отсутствуют циклы, следовательно, граф является деревом.

Оба доказательства показывают, что связный граф с ( n ) вершинами и ( n-1 ) рёбер действительно является деревом.