У любого графа сумма степеней всех вершин – есть число чётное, равное удвоенному числу рёбер графа.

Доказательство:

Пусть n- число вершин графа, k – число рёбер.

, т.к. каждое ребро принадлежит двум вершинам, следовательно:

. чтд

Следствие:

Число нечётных вершин графа чётно (если сумма n слагаемых – число чётное, то среди них нечётных слагаемых может быть только чётное число)

Задача:

Можно ли 15 телефонов соединить между собой так, чтобы каждый был связан ровно с 9-ю другими?

N=15, стА_i = 9.

Выходит противоречие следствию, т.к нечётное число вершин (15) имеют нечётную степень (9).

Ответ: не возможно.

Теорема2:

У любого графа с числом вершин n≥2 имеются хотя бы 2 вершины одинаковой степени.

Доказательство:

Каждому из шахматистов поставим в соответствие вершину графа, соединим рёбрами попарно вершины, соответствующие шахматистам уже сыгравшим между собой партию.

Каждая вершина графа с n вершинами может иметь степень равную 0,1,2,…,(n-1). предположим, что существует граф, все вершины которого имеют разную степень, т.е. каждое из чисел последовательности 0,1,2,…,(n-1) является степенью одной и только одной из его вершин. Но этого не может быть, т.к. если в графе есть вершина А со степенью 0, то в нём не найдётся вершина B cо степенью (n-1), т.к. эта вершина д.б. соединена рёбрами со всеми вершинами, включая вершину A. Т.е. не могут в графе находится одновременно вершины со степенью 0 и (n-1), а значит, не могут все вершины иметь разную степень и есть хотя бы две вершины с одинаковой степенью. чтд

Теорема 3:

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

Доказательство:

1. Допустим, что всё же найдётся граф с n вершинами, в котором ровно 2 вершины изолированы (т.е. степени 0), а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолирование вершины, останется граф с (n-1) вершинами, степени которых не совпадают. Но такого графа не существует по теореме 2, значит предположение не является верным.

2. Допустим, что существует граф с n вершинами, в котором ровно 2 вершины имеют степень (n-1), а все остальные несовпадающие степени. Рассмотрим дополнение этого графа до полного графа. Тогда эти две вершины (которые имели степень (n-1)) будут иметь степень 0, а этого не может быть из 1-ой части доказательства. чтд