Задача 8.10

Відповідь: 196

Перелік задач

Відповідь: 196

Рішення:
Покажемо, що 196 рейсів в країні може бути. Для цього виберемо якісь два міста і з'єднаємо кожен з них прямими авіарейсами з рештою 98 містами. Легко бачити, що умову задачі виконано.

Тепер доведемо, що в країні не може бути меншого числа авіарейсів. Розглянемо вершину A найменшій мірі. Очевидно, ця ступінь не менш 2. Якщо ця ступінь ≥ 4, то розглянутий граф має не менш 100 * 4/2 = 200 ребер.

Якщо ступінь A дорівнює 2, а B і C - суміжні з A вершини , то всі інші 97 вершин (як і A) з'єднані і з B, і з C, тому в графі не менше 196 ребер.

Нарешті, нехай ступінь A дорівнює 3, а B, C, D - суміжні з A вершини. Тоді кожна з решти 96 вершин з'єднана хоча б з двома з вершин B, C, D, і в графі не менше 3 + 2 * 96 = 195 ребер.

Але якщо інших ребер немає, то будь-які дві з решти 96 вершин повинні бути з'єднані з однією і тією ж парою з трійки B, C, < i> D.

Значить, що залишилася з цих трьох вершин суміжно лише з A. Таким чином, знайшлася вершина ступеня 1. Але, як було сказано вище, такого бути не може.