Степень вершины. Степень графа

Пусть - некоторый граф.
Степенью вершины называется величина - число дуг, инцидентных данной вершине. Степенью графа называется величина . Минимальною степенью графа называется величина .

Пример

Теорема
Сумма степеней вершин графа есть число четное: .
Следствие
Число вершин с нечетными степенями – четно.

Граф называется регулярным, если степени всех его вершин равны.

Пример

Регулярный граф степени 2

Для орграфов:

- полустепень исхода.
- полустепень входа.

Теорема
Для любого орграфа .

Пример

Распределение степеней вершин совпадает, но графы не изоморфны.

Типы графов

Граф и ограф.

Граф (граф, построенный на вершинах и ребрах).

3. Полный граф на вершинах (все вершины смежны между собой).
Пример ( )