Доведення: Кількість ребер графа дорівнює половині суми ступенів його вершин. Оскільки кількість ребер має бути цілим числом, то сума ступенів вершин має бути парною. Mar 4, 2013

Число ребер в повному графі n(n-1)/2. Графи рівні, якщо безліч вершин та інцидентних їм ребер збігаються. Графи, що відрізняються тільки нумерацією вершин і реберназиваються ізоморфними. Граф називається регулярним (однорідним), якщо ступеня всіх його вершин рівні.

Один із них має 40 ребер і є 5-регулярним графом, інший має 80 ребер і є 10-регулярним графом.

У додатковому графі до. кількість ребер дорівнює. Оскільки безлічі ребер в G і G диз'юнктні, то |E|+|¯E|= , з чого слід затвердження теореми.