В связных графах количество вершин и рёбер связано следующим образом: в связном графе с n вершинами не меньше n−1 рёбер. 5

Также существует лемма, которая гласит, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер. 12