Степени вершины

Если в графе пара вершин такова, что , то вершины называются смежными; в этой ситуации каждая из них называется инцидентной ребру , а ребро называется инцидентным каждой из вершин . Если вершина и ребро инцидентны, то пишут .

Количество ребер, инцидентных данной вершине , называется ее степенью или локальной степенью графа в вершине иобозначают через . Для неориентированного графа . Вершина с нулевой степенью называется изолированной. Вершина, степень которой равна единице, называется висячей.

Если ребро (дуга) инцидентно только одной вершине, то его называют петлей. Ребра называют кратными, если они инцидентны одним и тем же вершинам.

Исторически первой теоремой теории графов является утверждение, принадлежащее Эйлеру и связывающее количество ребер, вершин и их степеней.

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

.

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

Следствие. В любом графе число вершин нечетной степени четно.

Доказательство. Пусть и – множества вершин четной и нечетной степени соответственно. Очевидно, что

.

Первое слагаемое четно (как сумма четных чисел). Значит второе слагаемое также должно быть четным, а это при суммировании нечетных чисел возможно, если только их количество четно.

Для орграфов вместо степени вершины вводят понятие полустепеней: полустепень исхода – это число дуг, выходящих из вершины ; полустепень захода – это число дуг, входящих в вершину . Очевидно, что

.