Теорема. Кількість вершин непарного ступеня будь-якого графа завжди є парною. Доведення: Кількість ребер графа дорівнює половині суми ступенів його вершин. Оскільки кількість ребер має бути цілим числом, то сума ступенів вершин має бути парною. Mar 4, 2013
Число ребер у повному графі n(n-1)/2. Графи рівні, якщо безліч вершин та інцидентних їм ребер збігаються. Графи, що відрізняються тільки нумерацією вершин і реберназиваються ізоморфними. Граф називається регулярним (однорідним), якщо ступеня всіх його вершин рівні.
тобто сума ступенів вершин будь-якого графа дорівнює подвоєному числу його ребер. Крім того, з формули випливає, що в будь-якому графі число вершин непарний ступеня парно. Дане твердження (і сама формула) відомі як лема про рукостискання.
На малюнках, що репрезентують граф, вершина зазвичай позначається кружком з міткою, ребро – лінією, дуга – стрілкою, що з'єднує вершини.