Упр.67 ГДЗ Бунимович Булычев 10 класс (Алгебра)

а) граф из семи вершин, в котором все вершины имеют степень 2;
б) граф из восьми вершин, в котором все вершины имеют степень 2;
в) граф из восьми вершин, в котором все вершины имеют степень 1;
г) граф из семи вершин, в котором все вершины имеют степень 1;
д) граф из семи вершин, в котором все вершины имеют степень 3;
е) граф из восьми вершин, в котором все вершины имеют степень 3.

1. Если все вершины графа имеют степень 2, то каждая вершина соединена ровно с двумя другими. Такой граф существует при любом числе вершин не меньше 3: это, например, простой цикл.

   Значит, для случаев а) и б) граф существует.

2. Если все вершины имеют степень 1, то сумма степеней всех вершин равна числу вершин. Но сумма степеней любого графа должна быть чётной, так как она равна удвоенному числу рёбер.

   Следовательно, граф с 8 вершинами и степенью каждой вершины 1 существует, а с 7 вершинами — не существует.

   Значит, для случаев в) граф существует, а для г) — нет.

3. Если все вершины имеют степень 3, то сумма степеней равна $$3n$$, где $$n$$ — число вершин. Эта сумма должна быть чётной, значит, $$3n$$ чётно, а значит, и $$n$$ должно быть чётным.

   При $$n=7$$ это невозможно, а при $$n=8$$ возможно.

   Значит, для случая д) граф не существует, а для е) — существует.

Примеры построения:

• для а) и б) — циклы из 7 и 8 вершин;
• для в) — 4 непересекающихся ребра, соединяющих 8 вершин попарно;
• для е) — любой 3-регулярный граф на 8 вершинах, например граф куба.

Ответ

а) существует; б) существует; в) существует; г) не существует; д) не существует; е) существует.