Степени

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

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

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

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

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

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

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