3. а) В турнире участвовали 6 команд, каждая сыграла с каждой ровно один раз. Сколько всего было сыграно игр? б) Существует ли граф с пятью вершинами, степени которых равны 3, 3, 3, 2, 1? Ответ объясните.

1. а) Каждая игра соответствует паре команд. Число пар из 6 команд: \(\frac{6\cdot5}{2}=15\).

2. б) Такого графа не существует. По лемме о рукопожатиях сумма степеней вершин любого графа равна удвоенному числу рёбер и потому чётна. Здесь сумма степеней равна \(3+3+3+2+1=12\), что само по себе условие выполняет, но последовательность степеней не реализуема: три вершины степени 3 должны быть соединены с четырьмя другими вершинами в общей сложности шестью рёбрами. При этом у оставшихся двух вершин степени 2 и 1 недостаточно степеней, чтобы обеспечить необходимые связи. Проверка алгоритмом Хавела—Хакими: \((3,3,3,2,1)\to(2,2,1,0)\); удаление вершины степени 2 потребовало бы уменьшить две оставшиеся степени, включая 0, что невозможно.

Ответ: а) 15 игр; б) такого графа не существует.