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

Подграфом простого графа (V,E) называется граф (V’,E’), такой, что V’ Í V, E’ÍE, и для всякого ребра g = {u,v}ÎE’ вершины u и v принадлежат E’.

Теорема   (теорема Эйлера о сумме степеней вершин графа)

Пусть d(v) обозначает степень вершины v. Для произвольного простого графа G = (V, E) верно соотношение:

.

Доказательство

Рассмотрим упорядоченные пары (v,g), состоящие из вершины v инцидентой ребру g. С одной стороны, количество таких пар равно сумме степеней вершин, с другой стороны, оно равно удвоенному числу ребер.

Замечание

Теорема Эйлера имеет место и для графов, не являющихся простыми.