Теория графов и комбинаторика

Граф (г называется одаюродшм (или регулярным), воли вое 0ГО вершины ИМ0ВЗТ одну и ту же отеггонь, при этом общая дяя воех вершин отепень нг.'^ннается отепенью графа и обоэначоетоя Очевидно, графы On и К» являютоя однородными Легко доказать, что дополнение регулярного графа также яв­ ляется p0гyляpнL.i графом, причем с/(&-) - IVI-i-J(f), Спранедагина следующая проотая Теорема 2 Л . В любом графа сумма отепеней воех воршин равна удвоэнному чис-у ребер, т . е . ( 2 Л ) ггб\/ Действительно, каждое ребро вносит в эту оумму две единицы. Напомним, Что каждая петля при вычислении степеней учитываетоя дважды. Таким образом, эта творв.„а - праводаива и для мультигра- фов и для поевдографов. Для однородного графа ОС/ = IVI я (&) . Следсгаи^. В любом графе чиоли вершин о начетны- ! ми отепенями четно. • Доказатальотво. Пуо!ГьУ={^, i/ }• _ множест- ; во вершин о нечетныш о т е п е н я м и ; ( 1 5 ^ } - множество вершин о Ч0ТНЫШ отепенями; УИ - чиолс вершин о нечетныш сте­ пенями. Тогда ^ ^ L'i K-f " (?=f Сумма в левой чаоти равенотна четна по теореме, вторая оумма в правой ласти четна как оумма четных слагаемых. Тогда и первая сумма правой части четна как разность четных чисел. Таким обра­ зом, является 40-юй суммой нечетных слагаемых. Следовагелько, количество слагаемых УЛ - четно. Что и требо­ валось доказать. Как следствие теоремы 2 . 1 можно получить следующее yTsapit- дение: •Любой кубический граф (однородный степеш! 3 ) имеет четное число, вершин. Для простых графов оправедзгаво следующее утверздение: Теопема 2.2. Любой граф, имеющий не менее двух вершин, со­ держит хотя бы две вершиш о одинаконы1;Ж степенями. Доказательство. Пуоть граф имеет f вершин С 1VI = f ) . Очевидно, \ f V ' € Y 4 С1Г) £ р-< ) . Допустим, что степени воех вершин различны. Тогда они равны чиолам 0,1,2, 13