logo
флеров

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

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

Пусть G - неориентированный граф. Число (x) ребер, инцидентных вершине x, называется локальной степенью, или просто степенью вершины x графа G. В каждом случае должно быть указано, считается петля однократной или двойной.

Пусть (a, b) = (b, a) - число ребер, соединяющих вершины a и b.

Очевидно, каждая степень каждой вершины есть сумма кратностей в вершине a:

.

Обозначим через ne = ne (G) число ребер в неориентированном графе G.

Так как каждое ребро учитывается в двух степенях в вершинах a и b, то. Формула остается справедливой и при наличии петель, если только в локальных степенях вершин считать их дважды. Поэтому

.

Отсюда следует

Теорема 3.1. 1 В конечном графе число вершин нечетной степени четно.

    1.