построить граф 8 вершин 1степени

Задача: построить граф на 8 вершинах, каждая вершина имеет степень 1.

Идея:

• Узел с степенью 1 должен быть соседем ровно одного другого узла. Значит граф состоит только из независимых пар вершин, связанных ребром.
• Это называется матчинг (совпадающее соединение). Для 8 вершин получится 4 пар и 4 ребра. Граф не будет связан, будет состоять из 4 компонентов, каждый из которых — граф с двумя вершинами и одним ребром (K2).

Пошаговое решение:

1. Обозначим вершины: v1, v2, v3, v4, v5, v6, v7, v8.
2. Соединим их в пары так, чтобы пары не пересекались:
   • Ребро (v1, v2)
   • Ребро (v3, v4)
   • Ребро (v5, v6)
   • Ребро (v7, v8)
3. Проверим степени:
   • deg(v1) = 1, deg(v2) = 1
   • deg(v3) = 1, deg(v4) = 1
   • deg(v5) = 1, deg(v6) = 1
   • deg(v7) = 1, deg(v8) = 1 Все вершины имеют степень 1.
4. Свойства полученного графа:
   • Число ребер: 4 (так как сумма степеней 8, а |E| = сумма степеней / 2 = 8/2 = 4)
   • Граф состоит из 4 компонент, каждая из которых — K2 (два связанных вершины).
   • Граф 1-регулярный (каждая вершина имеет степень 1).
   • Граф разобщённый; не является связным. Также он бипартитен (каждая компонента состоит из одного ребра).

Вариант изображения (ASCII): v1 -- v2 v3 -- v4 v5 -- v6 v7 -- v8

или в виде списка смежности: v1: {v2} v2: {v1} v3: {v4} v4: {v3} v5: {v6} v6: {v5} v7: {v8} v8: {v7}

Дополнительно:

• Это единственный по изоморфизму класс 1-регулярного графа на 8 вершинах: разложение на 4 несокращённых ребра (4 K2). Другие варианты будут изоморфны этому, только метки вершин разные.

Если хочешь, могу привести ещё один конкретный пример пары вершин (например, v1–v8, v2–v7, v3–v4, v5–v6) и проверить степени.