Таблицы Брадиса

Полученное противоречие доказывает утверждение задачи.

Полученное противоречие доказывает утверждение задачи.

Элементы математики в задачах - Г. А. Мерзон

 

 

0        0 10 11 10 32 33 21

 

О     О

136

2        2

2 О

 

 

 

Задача 8. Докажите, что в графе с более чем одной вершиной есть две вершины одинаковой степени.

Решение. Допустим, существует граф с п > 1 вершинами, в котором степени всех вершин различны. Степень каждой из этих вершин — целое число от 0 до п — 1, всего п вариантов. Поскольку степени всех вершин различны, в графе есть одна вершина степени 0, одна степени 1, ..., одна степени п — 1. Рассмотрим вершины степени 0 и п — 1. Так как п > 1, это разные вершины. Но вершина степени 0 не соединена ни с одной вершиной, а вершина степени п — 1 соеди­нена со всеми вершинами. Поэтому эти две вершины одновременно соединены и не соединены между собой. Полученное противоречие доказывает утверждение задачи.

Задача 9. Докажите, что сумма степеней вершин произвольного гра­фа равна удвоенному количеству его ребер.

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