Доказать признак связности неорграфа

[HenryDukart]

Доказать, что если степень каждой вершины n-вершинного графа без петель $\ge\frac{n-1}{2}$ то он связен. Вот задача. Я дорылся до того, что в любом связном неорграфе количество ребер $\ge n-1$, где $n$ - количество вершин ($n\ge1$). Я пытался доказать от противного: условие выполняется, но граф несвязный. А это значит, что он состоит из $k$ компонент связности ($k\ge2$). Тогда количество ребер исходного графа $\ge n-k$. Вот тут я и застопорился: не могу связать степени никак. Помогите, пожалуйста.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»