В графе две вершины имеют степень 13, восемь вершин — степень 12. Сколько ребер в этом графе?

Для того чтобы найти количество рёбер в графе, можно воспользоваться свойством графа, связывающим степени его вершин с количеством рёбер.

Обозначим количество рёбер графа через $E$, а количество вершин через $V$. По теореме о сумме степеней всех вершин в неориентированном графе сумма степеней всех вершин равна удвоенному количеству рёбер. То есть:

Здесь $\text{deg}(v_i)$ — степень вершины $v_i$, а $E$ — количество рёбер.

В данном случае:

• Две вершины имеют степень 13, значит, их суммарная степень будет $2 \times 13 = 26$.

• Восемь вершин имеют степень 12, значит, их суммарная степень будет $8 \times 12 = 96$.

Итак, общая сумма степеней всех вершин:

Теперь, зная сумму степеней вершин, можно найти количество рёбер:

Разделив обе части на 2, получаем:

Таким образом, в графе 61 ребро.