Изменения

Действительно, так как степень каждой вершины нечетна, то число вершин в графе четно(так сумма степеней всех вершин четна). Пусть <tex> n = 2r </tex>, то равенство принимает вид <tex>|E| =\frac{kn}{2} = \frac{2kr}{2}=kr </tex>, то есть количество ребер кратно <tex> k</tex>.

* Lecture Notes on Graph Theory By Tero Harju, Department of Mathematics University of Turku, 2011 — с. 7-8

* [http://en.wikipedia.org/wiki/Handshaking_lemma Handshaking lemma — Wikipedia]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Основные определения теории графов]]