Локальные степени вершин

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

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

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

(1)

где - множество ребер графа , - число элементов множества . Таким образом, сумма стоящая в правой части равенства (1), является четной. Эта сумма останется четной и после удаления из нее всех четных локальных степеней . Поэтому число оставшихся слагаемых, отвечающих нечетным локальным степеням , должно быть нечетным.

Заметим, что утверждение теоремы остается верным и для неориентированных графов с петлями, если каждую петлю считать дважды.

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

Не нашли, что искали? Воспользуйтесь поиском: