ОТВЕТЫ, УКАЗАНИЯ, РЕШЕНИЯ

1.1.10.

1.5. Указание.Подсчитать количество рёбер в полном графе с 87 вершинами.

1.7. 4094.

1.9. Указание. Подсчитать количество рёбер в соответствующем графе.

1.10. Указание. Использовать лемму о рукопожатиях.

1.18. (а) 120, (б) 176, (в) 1024, (г) 45, (д) 56, (е) 1023.

1.19. (а) 66, (б) 79, (в) 4096, (г) 220, (д) 299, (е) 4095.

1.20. 10.

1.24. Указание. Использовать тот факт, что если F- самодополнительный граф, то F и содержат одинаковое количество рёбер.

1.35, 1.36. Указание. Использовать лемму о рукопожатиях.

1.37. 198.

1.59.(а) эйлеров, гамильтонов, (б) гамильтонов, (в) эйлеров.

1.64.(а) n!, (б) (n -1)!

1.65.(а) 0.5*n!, (б) 0.5*(n -1)!

1.66. Указание. Предположив, что мост существует, удалить его.

1.81. Решение.Доказательство проводится по индукции - отдельно для чётных и нечётных значений n. Ограничимся чётными.

Для малых значений n утверждение очевидно.

Пусть верно для всех чётных значений n £ 2p. Докажем это утверждение для не содержащего треугольников графа F с n = 2p+2 вершинами. Выберем в F две смежные вершины u и w. Подграф F* = F - {u, w} содержит 2p вершин и не имеет треугольников, так что, по предположению, в нем, самое большее, [4p²/4] = p² ребер.

В графе F нет вершины, смежной с вершинами u и w одновременно (иначе существовал бы треугольник). Значит, если вершина u смежна с l вершинами графа F*, то вершина w может быть смежна, самое большее, с 2p - l вершинами, следовательно, в F не больше чем p² + l + (2p - l) + 1 = (p+1)² = n ² / 4 = [n ² / 4] вершин.

1.82. Указание.Использовать утверждение задачи 1.81.

1.95. Если n чётное, то 2, иначе 3.

1.99. Указание.Индукцией по числу прямых.

1.100. Решение.Доказательство проводится по индукции.

При n = 1: D(F) = 0, c(F) = 1.Пусть утверждение верно при n = k. Докажем, что оно верно и для графа F* с k+1-й вершиной.

Удалив одну из вершин u графа F*, получим граф F, для которого, по предположению, c(F) £ 1+D(F). Так как D(F) £ D(F*), то c(F) £ 1+D(F*).

Вершина u соединена, как максимум, с D(F*) другими вершинами. Значит, среди 1+D(F*) цветов найдется хотя бы один для правильной раскраски вершины u, т.е. c(F*) £ 1+D(F*).

1.101. Любой несвязный граф.