Приёмы доказательств в теории графов

<<- Назад к вопросам

Какой метод использован при доказательстве следующей теоремы?

Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени.

Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким образом, граф содержит вершины степеней 0, 1,…, n-1. Наличие вершин степени 0 и n-1 даёт противоречие.

(Отметьте один правильный вариант ответа.)

Варианты ответа
Метод резолюции
Доказательство по индукции
Доказательство от противного (Верный ответ)
Метод натурального исчисления
Похожие вопросы
Доказательство теоремы Дирака осуществляется методом:
Укажите двудольные графы с паросочетанием из 2 рёбер: