2014-02-02
4212
Степень 
вершины u – это число ребер, инцидентных вершине u. Вершина u называется изолированной (концевой), если 
(
).
Следующая теорема была первой в истории теории графов (1936 г.)
Теорема (Л.Эйлер). Сумма степеней всех вершин (
)-графа равна удвоенному числу его ребер: 
.
Доказательство. При пересчете ребер, инцидентных всем вершинам, каждое ребро считается два раза.
Следствие. В графе число вершин с нечетными степенями четно.
Доказательство. Пусть вершины 
имеют нечетные степени, а 
вершины – четные степени. Тогда
.
