Теория графовДеревьяСвязность

Мосты

Стартовый архив Mathforces · задача Q

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

Докажите, что в связном графе без циклов с n вершинами ровно n−1 ребро.

Официальное решениеОткрыть

Докажем индукцией. При n=1 рёбер 0. В любом конечном дереве с n>1 есть лист. Удалим лист и единственное инцидентное ему ребро: останется связный граф без циклов на n−1 вершине. По предположению в нём n−2 ребра, значит в исходном n−1.

Отправить решение

Наберите не меньше 90 баллов, чтобы задача попала в решённые. Попытки сохраняются.

Войдите в аккаунт, чтобы отправлять решения и сохранять прогресс.

Обсуждение

Войдите, чтобы оставить комментарий.

Пока нет комментариев. Начните обсуждение.