Одноклассники Андрей, Богдан, Вадим, Григорий, Дмитрий и Евгений устроили турнир по настольному теннису и решили играть каждый с каждым. Турнир ещё не закончен. Рёбра графа показывают, кто с кем сыграл к этому моменту.
Больше всех партий сыграли Евгений и Григорий — по три партии. Вадим пока не сыграл ни одной партии, а Андрей, Богдан и Дмитрий сыграли по две. Можно сказать, что в графе степень вершины В равна 0, степени вершин А, Б, Д равны 2, а степени вершин Г и Е равны 3.
Степенью или валентностью вершины в графе называется количество исходящих из неё рёбер.
На рисунке два графа. В них по 4 вершины и по 3 ребра. Но эти графы не одинаковы: на рисунке а есть вершина степени 3, а на рисунке б такой вершины нет.
Вывод: если в двух графах поровну вершин и поровну рёбер, то такие графы не обязательно одинаковы.
Кратные рёбра в графе — два или более ребра, которые соединяют одни и те же две вершины.
Иногда приходится рассматривать граф с петлёй, то есть ребром, которое исходит из вершины и входит в неё же, то есть соединяет вершину саму с собой. При подсчёте степени вершины такое ребро считается дважды. На рисунке показан граф с петлёй. Степень вершины С равна 4.
Теорема о сумме степеней вершин:
В любом графе сумма степеней всех вершин является чётным числом.
У каждого ребра два конца, поэтому сумма степеней всех вершин в два раза больше числа рёбер, то есть чётное число.
Лемма 1:
Число ребер в графе ровно в два раза меньше, чем сумма степеней вершин.
Любое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер, т. к. каждое ребро было подсчитано дважды.
Лемма 2:
Сумма степеней вершин графа четна.
Это утверждение становится понятным, если вспомнить , что по лемме 1 эта сумма равна удвоенному количеству ребер.
Лемма 3:
Число нечетных вершин графа четно.
Если в графе есть n четных и k нечетных вершин, то сумма степеней четных вершин четна как сумма четных чисел. Сумма степеней нечетных вершин нечетна, если их количество k нечетно. Но тогда общее число степеней вершин тоже нечетно, чего не может быть. Значит k четно.
ДЗ здесь