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

Ответ: a) 0; в) 2; г) 3; д) 4

Теорема о рукопожатиях утверждает, что сумма степеней всех вершин графа равна удвоенному числу рёбер, следовательно, эта сумма должна быть чётной. Это означает, что количество вершин нечётной степени должно быть чётным.

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

Ответ: а) 0; в) 2; д) 4