Степени

Степенью вершины vi в графе G - обозначается di или deg vi- называется число ребер, инцидентных vi. Поскольку каждое ребро инцидентно двум вершинам, в сумму степеней вершин графа каждое ребро вносит двойку. Таким образом, мы приходим к утверждению, которое установлено Эйлером [2] и является исторически первой теоремой теории графов.

Теорема..2,1, Сумма степеней вершин графа G равна удвоенному числу его ребер:

Следствие 2.1 (а). В любом графе число вершин с нечетными степенями четно

В (р, q)-графе 0<deg< p-1 для любой вершины v. Минимальная степень вершин графа G обозначается через min deg G или d(G), максимальная — через max deg G= D(G). Если d(G) = D(G)=r, то все вершины имеют одинаковую степень и такой граф G называется регулярным (или однородным) степени r. В этом случае говорят о степени графа и пишут degG = r.

Регулярный граф степени 0 совсем не имеет ребер. Если G — регулярный граф степени 1, то каждая его компонента содержит точно одно ребро; в регулярном графе степени 2 каждая компонента — цикл, и, конечно, обратно. Первые интересные регулярные графы имеют степень 3; такие графы называются кубическими. На рисунке показаны два регулярных графа с 6 вершинами.

Следствие 2.1 (б). Каждый кубический граф имеет четное число вершин.

Полезно дать названия вершинам с малыми степенями. Вершина v называется изолированной, если deg u=0, и концевой (или висячей), если deg u=1.