Формула для связи количества рёбер с количеством вершин и степеней вершин в графе гласит, что сумма степеней всех вершин графа равна удвоенному количеству рёбер. 15

Обозначим: V — количество вершин, E — количество рёбер, d(v) — степень вершины v. 1 Тогда формула выглядит так: ∑ d(v) = 2E (где сумма берётся по всем вершинам графа). 1

Также можно сказать, что количество рёбер графа равно сумме степеней всех его вершин, делённой на 2. 2

Это утверждение называют теоремой о рукопожатиях. 5 Если сложить степени всех вершин графа, то каждое ребро внесёт в эту сумму вклад, равный 2. 5