Смежность, инцидентность

Две вершины и , где V – множество вершин графа G, называются смежными, если они соединены ребром. Два ребра называются смежными, если они имеют общую вершину.

Если вершина является концом ребра, то вершина и ребро называются инцидентными.

Число ρ(v) ребер, инцидентных вершине v, называется степенью этой вершины v.

Степень изолированной вершины равна нулю. Степень изолированной вершины, содержащей одну петлю, равна 2.

Вершина, степень которой равна 1, называется висячей.

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

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

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

где n – число вершин графа;

ρ(i) – степень i-й вершины графа (i = 1, 2, …, n).

Граф без петель называется полным, если каждая пара его вершин соединена одним ребром.

Степень любой вершины полного графа равна n–1,

где n – число его вершин, так как каждая вершина соединена ребрами с остальными вершинами графа. Отсюда следует, что число K ребер полного графа равно: