Граф можно задать матрицей смежности, которая представляет собой квадратную матрицу порядка m, где  m - число вершин графа. Элементы матрицы смежности p_ij (i,j=1,…m) определяются по следующему правилу:

.                                        (1)

Степенью вершины deg(v) в графе G называется число ребер, инцидентных вершине v. Для вершины орграфа deg(v)=od(v)+id(v), где полустепень исхода od(v) - число дуг, начинающихся (исходящих) из v, и полустепень захода id(v) - число дуг, заканчивающихся (заходящих) в v. Нетрудно убедиться, что имеют место равенства

                                     _m

                       deg(v_i)=Sp_ij                                                                                                                   (4)

                                    _j=1

и

                                   _{m                                   m}

                     od(v_i)= Sp_ij,     id(v_i) = Sp_ki,                                                   (5)

                                                    ^{j=1                                 k=1}

которые позволяют вычислять степени вершин через элементы матрицы смежности.

Вершины, у которых deg(v)=1, называют висячими (концевыми) вершинами. Ребро, инцидентное концевой вершине, также называется концевым. В предыдущем примере концевыми вершинами оказались v₃ и v₅, концевыми ребрами  - {v₂,v₃}  и {v₅,v₆}. Если в графе имеется вершина, у которой deg(v)=0, то она называется изолированной.

С понятием степени вершины связан первый результат, полученный Л.Эйлером (L.Euler) в теории графов.

Сумма степеней всех вершин графа есть четное число, равное удвоенному числу его ребер.