Степень графа — это количество рёбер, которые выходят из определённой вершины графа. 1

Степень нужна в теории графов для анализа свойств графа, таких как плотность связей или распределение степеней вершин. 4 Например, с её помощью можно определить, существует ли граф, если известно только количество нечётных вершин в нём, благодаря следствию из леммы о рукопожатиях. 1

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

Ещё одна задача, для которой нужна степень графа, — решение задач оптимизации, нахождение оптимальных путей и решений для различных процессов. 4