В данной задаче рассматривается граф, в котором степень каждой вершины равна ( k ), и количество вершин в графе равно ( n ). Давайте проанализируем, какие значения ( n ) и ( k ) могут быть совместимы, исходя из свойства графа.
Для любого простого графа (без петель и кратных рёбер), сумма степеней всех вершин равна удвоенному количеству рёбер. Это можно записать следующим образом:
[
\sum_{i=1}^{n} \text{deg}(v_i) = 2m,
]
где ( m ) - количество рёбер в графе. Если же все вершины имеют одинаковую степень ( k ), то:
[
n \cdot k = 2m.
]
Из этого уравнения следуют следующие ограничения:
- ( n \cdot k ) должно быть четным, поскольку ( 2m ) является четным числом. Это значит, что произведение ( n ) и ( k ) должно быть четным.
Теперь проанализируем предложенные варианты:
( n = 100 ), ( k = 99 ):
[
100 \cdot 99 = 9900 \quad (\text{четное}).
]
( n = 101 ), ( k = 99 ):
[
101 \cdot 99 = 9999 \quad (\text{нечетное}).
]
( n = 101 ), ( k = 98 ):
[
101 \cdot 98 = 9898 \quad (\text{четное}).
]
Таким образом, не может быть, чтобы ( n = 101 ) и ( k = 99 ), так как произведение будет нечетным.
Ответ: вариант ( n = 101, k = 99 ).
