4. Решите задачу по выявлению связности компонент графа

В компании из 7 мальчиков каждый имеет среди остальных не менее трех братьев. Докажите, что все семеро — братья.

Решение: возьмём любых двух мальчиков из этой компании. Предположим, что они не братья. Тогда каждый из них имеет среди оставшихся по три брата. По принципу Дирихле¹, у них есть общий брат, а значит, они братья. Итак, любые два мальчика из этой компании - братья, что и требовалось доказать.

5. Докажите, что граф с n вершинами, степень каждой из которых не менее (n - 1)/2, - связен.

Решение: рассмотрим две произвольных вершины и предположим, что они не соединены путем, то есть такой последовательностью ребер, в которой начало очередного ребра, совпадает с концом предыдущего. Каждая из этих двух вершин по условию соединена не менее, чем с (n - 1)/2 другими; при этом все упомянутые вершины различны - ведь если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины. Таким образом, мы указали не менее (n - 1)/2 + (n - 1)/2 + 2 = n + 1 вершин. Противоречие.

6.Определите, являются ли данные графы деревьями:

Ответ: да, все указанные графы являются деревьями согласно свойствам деревьев.

Задания для самостоятельного выполнения

3.1.1. Докажите, что валентности вершин графов А и Б совпадают.

А Б

3.1.2. Заданы два графа G₁(V₁, E₁) и G₂(V₂, E₂). Выясните, изоморфны ли графы?

3.1.3. Докажите, что графы А и Б изоморфны.

А Б

3.1.4. Определите, являются ли данные графы деревьями, почему?