Простые графы и их свойства

Ниже повсюду мы будем рассматривать графы, у которых между любыми двумя вершинами существует не более одного инцидентных им ребра. Ребра можно рассматривать как пары g={u,v}. Напомним, что такие графы называются простыми. Иногда мы будем называть их просто графами.

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

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