Вопрос:

7. В графе из каждой вершины выходит 4 ребра. Может ли в нём быть 10 рёбер?

Ответ:

Пусть в графе \(n\) вершин. Сумма степеней вершин равна \(4n\), а также равна удвоенному числу рёбер:

\[4n=2\cdot10=20.\]

Отсюда \(n=5\). Граф с 5 вершинами, в котором степень каждой вершины равна 4, является полным графом \(K_5\), в нём действительно \(\frac{5\cdot4}{2}=10\) рёбер.

Ответ: да.

Подать жалобу Правообладателю

Похожие