Какой может быть сумма степеней всех вершин графа, если в нём всего одно ребро?

Краткий ответ: 2.

Как это устроено

Степень вершины — это число рёбер, которые из неё выходят (петля считается дважды). Посмотрим, что даёт единственное ребро:

• оно соединяет две вершины (пусть \(A\) и \(B\));
• у \(A\) появляется одно ребро, значит \(\deg A = 1\);
• у \(B\) тоже \(\deg B = 1\);
• все остальные вершины, если они есть, ни с чем не соединены: их степень \(0\), на сумму они не влияют.

Поэтому \[ \deg A + \deg B = 1 + 1 = 2. \]

Общее правило (лемма о рукопожатиях)

Каждое ребро «приносит» по единице в степень сразу двух вершин, то есть увеличивает общую сумму на 2: \[ \sum \deg v = 2 \cdot m, \] где \(m\) — число рёбер. При \(m = 1\) получаем \(2 \cdot 1 = 2\).

Проверка

Даже если разрешена петля (ребро из вершины в неё саму), она даёт \(+2\) степени одной вершины, и сумма всё равно остаётся 2. Так что ответ единственный — 2.

Как решать похожие: считай не «по одной вершине», а по рёбрам — сумма степеней всегда вдвое больше числа рёбер.