67. Постройте граф рукопожатий, если друг другу пожали руки: а) 5 человек; б) 6 человек. Сколько рёбер в построенных графах?

Каждого человека изображаем вершиной, а каждое рукопожатие — ребром между двумя соответствующими вершинами. При рукопожатии каждый участник здоровается со всеми остальными.

1. а) Граф — полный граф на пяти вершинах: у каждой вершины степень 4. Число рёбер: \(\frac{5\cdot4}{2}=10\).
2. б) Граф — полный граф на шести вершинах: у каждой вершины степень 5. Число рёбер: \(\frac{6\cdot5}{2}=15\).

Ответ: а) 10 рёбер; б) 15 рёбер.