На рисунке изображен граф. Сколько вершин в этом графе имеют наименьшую степень?

Решение:

Степень вершины графа — это количество рёбер, исходящих из неё.

Посчитаем степени каждой вершины:

• Степень вершины A: 2 (рёбра AH, AE)
• Степень вершины E: 2 (рёбра EA, ED)
• Степень вершины D: 3 (рёбра DE, DB, DG)
• Степень вершины B: 2 (рёбра BD, BC)
• Степень вершины C: 3 (рёбра CB, CH, CF)
• Степень вершины F: 1 (ребро FC)
• Степень вершины H: 3 (рёбра HA, HC, HE)
• Степень вершины G: 1 (ребро GD)

Наименьшую степень имеют вершины F и G. Таких вершин 2.

Ответ: 2