Степень вершины. Теорема Эйлера о сумме степеней всех вершин.

Степень вершины u – это число ребер, инцидентных вершине u. Вершина u называется изолированной (концевой), если ().

Следующая теорема была первой в истории теории графов (1936 г.)

Теорема (Л.Эйлер). Сумма степеней всех вершин ()-графа равна удвоенному числу его ребер: .

Доказательство. При пересчете ребер, инцидентных всем вершинам, каждое ребро считается два раза.

Следствие. В графе число вершин с нечетными степенями четно.

Доказательство. Пусть вершины имеют нечетные степени, а вершины – четные степени. Тогда

.