10.2.3. Оценка числа эйлеровых графов

ЛЕММА В любом графе число вершин нечетной степени четно,

доказательство

По теореме Эйлера ]Г d(v) = 2q, то есть сумма степеней всех вершин — четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, значит, их четное число. П

Пусть д(р) — множество всех графов с р вершинами, а £(р) — множество эйле­ровых графов с р вершинами.

ТЕОРЕМА Эйлеровых графов почти нет, то есть

доказательство

Пусть £'(р) — множество графов с р вершинами и четными степенями. Тогда по предыдущей теореме £(р) с £'(р) и |£(р)| ^ |£'(р)|- В любом графе число вершин нечетной степени четно, следовательно, любой граф из £'(р) можно получить из некоторого графа S(p — 1), если добавить новую вершину и соединить ее со всеми старыми вершинами нечетной степени. Следовательно, |£'(р)| < |S(p — 1)|. Но |S(p)| = 2^с(^р'²). Заметим, что

C(fc,2)-C(fc-l,2)= ^ ^№"^П!

(fc-l)(fc-fc

2\(k - 2)! 2!(fc - 3)! fc(fe-l) (fc-l)(fc-2)

Далее имеем:

|S(P - 1)1 =