В неориентированном графе количество вершин, рёбер и степень вершин связаны следующим образом: сумма степеней всех вершин равна удвоенному числу рёбер в графе. 24

Степенью вершины называют число инцидентных ей рёбер (при этом петли считают дважды). 23 Любому ребру соответствует ровно две вершины. 1

Например, если в графе n вершин, то степень каждой из них равна n–1, а число рёбер можно посчитать по формуле n(n–1)/2. 2