Подграфом, натянутым на множество вершин графа

G, называется подграф, содержащий вершины из V и все ребра графа G, соединяющие пары вершин из

Подграф , состоящий из всех ребер, инцидентных вершине называется звездой вершины

Для графов без петель степень вершины α есть число ребер в звезде Zα. Очевидно, что сумма степеней всех вершин графа без петель равна удвоенному числу ребер.