2020-01-14
379
Лемма: В любом графе число вершин нечётной степени чётно.
Доказательство: По теореме 1 сумма степеней всех вершин число чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их чётное число.
Пусть G(p) – множество всех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.
Теорема 6: Эйлеровых графов почти нет, то есть
lim 
Доказательство: Пусть E/ (р) – множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ/(p) и |Е(р)|£|Е/(p)|.В любом графе число вершин нечётной степени чётно, следовательно, любой граф из Е/(p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всеми старыми вершинами нечётной степени. Следовательно, |Е/(p)| £|G(p-1)|. Но |G(p)|=2C(p, 2). Заметим, что
С(k,2)-C(k-1,2)=
= 
Далее имеем:
|Е(р)|£|Е/(p)| £|G(p-1)| = 2C(p-1,2) =2C(p,2)-(p-1) = |G(p)|2-(p-1)
и
, откуда lim 
. [3]
