Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3. Может ли количество вершин нечётной степени в каком-нибудь графе равняться 3?

Для решения задачи воспользуемся «Леммой о рукопожатиях», которая гласит: сумма степеней всех вершин графа равна удвоенному количеству его рёбер. Из этого следует, что сумма степеней всегда чётная, а значит, количество вершин с нечётной степенью в любом графе должно быть чётным. 1. **Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.** Проверим сумму степеней: $1+1+2+2+3+3 = 12$. Сумма чётная, значит такие графы существуют. Неодинаковые (неизоморфные) графы можно построить, по-разному соединяя вершины. * **Первый вариант:** Две несвязанные части. Первая — «треугольник» с «хвостом» (вершины со степенями 3, 2, 2, 1). Вторая — две вершины, соединённые одним ребром (степени 1, 1). В сумме: (3, 2, 2, 1) и (1, 1). * **Второй вариант:** Один связный граф в виде кольца из 4 вершин (степени 2, 2, 2, 2), где две вершины соединены дополнительной перемычкой (степени 3, 3) и к ним добавлены «висячие» вершины (степени 1, 1). 2. **Может ли количество вершин нечётной степени в каком-нибудь графе равняться 3?** **Ответ: Нет.** Согласно Лемме о рукопожатиях, сумма степеней всех вершин равна $2E$ (где $E$ — число рёбер), то есть числу чётному. Сумма чётных степеней всегда чётна. Чтобы общая сумма была чётной, сумма нечётных степеней тоже обязана быть чётной. Это возможно только если количество слагаемых (вершин с нечётной степенью) чётное ($2, 4, 6, \dots$). Число 3 — нечётное, поэтому такой граф существовать не может.