4. Три вершины графа имеют степень 4, ещё четыре — степень 5. Остальные девять вершин имеют одинаковую степень N. При каком наибольшем N такое возможно?

Всего в графе \(3+4+9=16\) вершин, поэтому степень любой вершины не превосходит 15.

По лемме о рукопожатиях сумма степеней должна быть чётной. Она равна \(3\cdot4+4\cdot5+9N=32+9N\), поэтому \(N\) должно быть чётным. Следовательно, \(N\leq14\).

Проверим, что \(N=14\) достижимо. Возьмём полный граф на 16 вершинах и удалим рёбра так, чтобы степени оставшихся вершин в дополнении были 11 у трёх вершин, 10 у четырёх и 1 у девяти. Такая последовательность степеней реализуема: в дополнении можно соединить каждую из девяти вершин степени 1 с отдельной вершиной из семи вершин больших степеней; степени семи вершин тогда станут 10, 9, 9, 9, 9, 9, 9. Их можно соединить между собой графом с этими степенями (например, дополнением цикла на семи вершинах с подходящим распределением степеней). Значит, в исходном графе можно получить степени 4, 5 и 14.

Ответ: \(N=14\).