4. Может ли количество вершин нечётной степени в каком-то графе равняться: а) 0; б) 1; в) 2; г) 4?

В любом конечном графе сумма степеней вершин равна удвоенному числу рёбер, поэтому она чётна. Следовательно, число вершин нечётной степени всегда чётное.

• а) 0 — да, например, в графе без рёбер;
• б) 1 — нет, число нечётных степеней не может быть нечётным;
• в) 2 — да, например, в графе из одного ребра и двух вершин;
• г) 4 — да, например, в пути из пяти вершин: у четырёх крайних и промежуточных некрайних? Степени такого пути — 1, 2, 2, 2, 1, поэтому нечётных вершин только две. Вместо этого возьмём граф из двух непересекающихся рёбер: у него четыре вершины степени 1.

Ответ: а) да; б) нет; в) да; г) да.