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

По теореме о сумме степеней число вершин нечётной степени в любом графе чётно. Поэтому:

• а) 0 — да, например в графе без рёбер;
• б) 1 — нет;
• в) 2 — да, например в графе из одного ребра;
• г) 3 — нет;
• д) 4 — да, например в графе из двух непересекающихся рёбер.