Предположим, что простой граф имеет 18 ребер, 4 вершины степени 3, а все остальные - степени 4. Сколько вершин у этого графа?

Простой граф не имеет ребер, соединенных от узла к самому себе, поэтому сумма степеней всех задействованных вершин будет 2 * 18 = 36. Сумма степеней вершин степени 3 равна 12, поэтому сумма степеней степени вершин степени 4 должны быть 36 - 12 = 24. Должно быть 24/4 = 6 вершин степени 4, всего в графе 10 вершин .

Вы можете построить такой граф следующим образом. Обозначьте вершины номерами от 1 до 10. Выполните следующие соединения:
(1-2-3-4-5-6-7-8-9-10-1)
(2-4)
(7-9)
(1- 5-8-1)
(3-6-10-3)
Вершины 2, 4, 7, 9 будут иметь степень 3. Остальные будут иметь степень 4. (Есть много других возможностей.)