Теоремы о степенях вершин и изоморфизм графов

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

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

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

Теорема 3.4.2. Число вершин нечетной степени в любом графе четно.

Доказательство: пусть число вершин в графе равно n. Не нарушая общности, предположим, что степени первых r вершин v ₁, v ₂,¼, v_r четны, а степени оставшихся n ‑ r вершин нечетны. Тогда общая сумма степеней всех вершин равна . По теореме 1 левая часть этого равенства – четное число. Первая сумма в правой части также четна, т.к. каждое слагаемое в этой сумме четно по предположению. Следовательно, и вторая сумма в правой части тоже четна. Но так как каждое слагаемое в этой сумме нечетно по предположению, то число этих слагаемых должно быть четным. Поскольку число этих слагаемых совпадает с числом вершин нечетной степени, то число последних четно.

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

Два графа G ₁ и G ₂ называются изоморфными, если существует биективное отображение между множествами их вершин и ребер такое, что соответствующие друг другу по этому отображению ребра графов G ₁ и G ₂ инцидентны соответствующим друг другу по этому же отображению парам вершин этих графов.

Другими словами, если вершины v_i и v_j графа G ₁ соответствуют вершинам v_i ¢и v_j ¢графа G ₂, то ребро е_k =(v_i, v_j) в G ₁ должно соответствовать ребру е_k ¢=(v_i ¢, v_j ¢) в графе G ₂ и наоборот.