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

Количество вершин нечётной степени в любом графе всегда чётное число. Это следует из того, что сумма степеней всех вершин равна удвоенному числу рёбер (лемма о рукопожатиях), и, следовательно, должна быть чётной. Чтобы сумма была чётной, количество нечётных слагаемых (то есть степеней нечётных вершин) должно быть чётным. Ответы: a) 0 - Да, возможно. б) 1 - Нет, невозможно. в) 2 - Да, возможно. г) 3 - Нет, невозможно. д) 4 - Да, возможно.