130. В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 3, 3; б) 0, 1, 2, 2, 3, 4. Сколько всего рёбер в этом графе?

По теореме о сумме степеней число рёбер равно половине суммы степеней.

а) \((2+2+3+3+3+3)/2=16/2=8\). Такая последовательность возможна: например, возьмём рёбра \(AB, AC, AD, BC, BD, CD, CE, EF\); степени будут \(3,3,3,3,2,2\).

б) Сумма степеней равна \(0+1+2+2+3+4=12\), значит, число рёбер равно \(12/2=6\). Однако в простом графе с 6 вершинами эта последовательность степеней невозможна: вершина степени 4 смежна с четырьмя вершинами, в том числе с вершиной степени 0, что противоречит её нулевой степени. Поэтому графа с указанными степенями нет; формальное вычисление по сумме дало бы 6 рёбер.

Ответ: а) 8 рёбер; б) 6 рёбер по сумме степеней, но графа с такой последовательностью степеней не существует.