Определение. Степенью вершины x_i графа G(X,T) называется число d_i, равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень - четное (нечетное) число.

Теорема 1. Если конечный граф G(X,T) (без петель) имеет n вершин и m ребер, то

.

Теорема 2. Число нечетных вершин любого графа четно.

Теорема 3. Во всяком графе с n вершинами (n >2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Теорема 4. Если в графе с n вершинами (n >2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n -1.