Ступеня і полустепені вершин графа
Ступені вершин ми будемо визначати для нерграфа, а полустепені для орграфа.
Глобальної ступенем вершини неорграфа називається число всіх ребер графа інцідентних цій вершині (dg (V)).
Локальної ступенем вершини неорграфа називається кількість всіх ребер графа інцідентних даної вершині, де при підрахунку кількості кожна петля розглянутої вершини вважається двічі (тому що при розтині петлі на 2 частини вона породжує 2 ребра) (dl (V)).
dl (V) = dg (V) + число петель на вершині V.
Т.обр. якщо на вершині петель немає, то dl (V) = dg (V).
Для орграфа природно визначити 2 види ступенів:
Полуcтепенью результату вершини орграфа називається число дуг цього графа включаючи і петлі, для яких дана вершина є початком. (D- (V)).
Полуcтепенью заходу вершини орграфа називається число дуг цього графа включаючи і петлі, для яких дана вершина є кінцем. (D + (V)).
Лемма про рукостискання Сума локальних ступенів усіх вершин кінцевого неорграфа - парне число, рівне подвоєному числу ребер.
Док-во: кожне ребро при додаванні ступенів вершин графа враховується двічі, тобто згадана сума всіх ступенів дорівнює подвоєному числу всіх ребер, тобто парна.
Теорема. у всякому кінцевому неоргафе без петель і кратних ребер, що має не менше двох вершин, знайдуться 2 вершини мають однаковий ступінь.
Док-во: Нехай існує граф має n> = 2 вершин, будь-які ступені вершин якого попарно різні.
Оскільки розглянутий граф простий, то ступеня його вершин не перевищують числа n-1 і тому збігаються з безліччю, значить в нашому графі є одна вершина ступеня 0 (тобто ізольована) і є вершина ступеня n-1, тобто пов'язана ребрами з іншими вершинами, тобто і з ізольованою, таким чином отримуємо протиріччя. Значить теорема вірна, ч.т.д.
однорідні графи
Неорграф називається однорідним ступеня однорідності k, якщо ступеня всіх його вершин збігаються з числом k (тобто рівні один одному). (Приклад такого графа- повний граф).
Затвердження: нехай n, m, k-відповідно число вершин, число ребер і ступінь однорідності деякого однорідного графа. Тоді ці три числа зв'язуються в формулу: k • n = 2m.
Зауваження: вказане твердження одно справедливо для однорідних графів без петель і з петлями (в останньому випадку під ступенем вершини розуміється локальна ступінь)