В графе 2n + 1 вершина, степень каждой равна n. Докажите, что после удаления любого подмножества из менее чем n рёбер получается связный граф.

Предположим, что после удаления не более n ребер получается несвязный граф. Тогда найдется компонента связности A, состоящая из a ≤ n вершин, т.к. если во всех компонентах связности хотя бы n + 1 вершина, то всего вершин хотя бы 2 · (n + 1) = 2n + 2 – противоречие.
Степень каждой вершины в компоненте не больше, чем a−1. Получим, что у каждой вершины было
удалено хотя бы n − a + 1 ребер, исходящих в вершины не в компоненте A. Тогда всего было удалено хотя бы a(n−a+1) ребер. По условию было удалено не больше n ребер, тогда имеем неравенство:
$ a(n − a + 1) < n ⇔ an − a^2 + a − n < 0 ⇔ n(a − 1) − a(a − 1) < 0 ⇔ (n − a)(a − 1) < 0 $
Но n ≥ a и a ≥ 1 ⇒ (n − a)(a − 1) ≥ 0
Получим противоречие, тогда изначальное предположение неверно. Тогда после удаления не более
n ребер граф останется связным.