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

Степенью (или валентностью) вершины графа G называется число инцидентных ей ребер, т. е. число вершин в ее окружении. Будем обозначать степень вершины v через deg G_v (или deg v). Тем самым deg v = |N (v) |. Максимальная и минимальная степени вершин графа G обозначаются символами D(G) и d(G) соответственно:

Список степеней вершин графа называется его степенной последовательностью. Порядок членов в этой последовательности роли не играет.

Вершина степени 0 называется изолированной, вершина степени 1 — концевой (или висячей). Ребро, инцидентное концевой вершине, также называется концевым. Вершина графа, смежная с каждой другой его вершиной, называется доминирующей.

Рассмотрим сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму 2, поэтому верно

Утверждение 5.1 («лемма о рукопожатиях»). Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер:

Возможная интерпретация этой леммы такова: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала).

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

Понятие степени вершины и лемма о рукопожатиях сохраняются для мульти- и псевдографов. При этом каждая петля вносит в степень соответствующей вершины двойку.