333
правки
Изменения
→Регулярный граф
==== Регулярный граф ====
В [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 регулярном графе ] с <tex> n </tex> вершинами, степени которых равны <tex> k</tex> (регулярный граф), ровно <tex>\frac{kn}{2} </tex> ребер.
'''Следствие.''' Если степень каждой вершины нечетна и равна <tex> k</tex>, то количество ребер кратно <tex> k </tex>.
'''Доказательство.''' Действительно, так как степень каждой вершины нечетна, то число вершин в графе четно(так сумма степеней всех вершин четна). Пусть <tex> n = 2r </tex>, то равенство принимает вид <tex>|E| =\frac{kn}{2} = \frac{2kr}{2}=kr </tex>, то есть количество ребер кратно <tex> k</tex>.
== Источники ==
