Задача
COM-B1-M09-P011 Слишком много ребер
#11
★★☆☆☆ Уровень 2 из 5
Может ли простой граф на \(8\) вершинах иметь \(29\) ребер?
Максимум достигается в полном графе.
В простом графе между двумя вершинами не более одного ребра. Максимум ребер - в полном графе \(K_8\), где их \(\binom{8}{2}=28\). Поэтому \(29\) ребер быть не может.
Фиксирует слово «простой граф».