logo search
флеров

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

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

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

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

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

.

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

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

.

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

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

    1.