Уровень с а) Необходимо доказать невозможность существования графа с пятью вершинами, без петель и кратных рёбер

Babochka

10

а) Чтобы доказать невозможность существования такого графа, нам следует воспользоваться свойством графов, которое гласит: сумма степеней всех вершин в графе должна быть равна удвоенному количеству ребер.

Пусть дан граф с пятью вершинами, и степени его вершин равны 4, 1, 3, 2 и 4. Обозначим эти вершины буквами A, B, C, D и E соответственно.

По условию степень вершины A равна 4. Это означает, что ребра из вершины A соединяются с 4 другими вершинами. Отметим эти вершины: B, C, D и E.

Теперь учтем, что степень вершины B равна 1. Это означает, что в графе должно быть только одно ребро, и оно должно соединять вершину B с одной из вершин A, C, D или E.

Теперь учтем, что степень вершины C равна 3. Мы уже соединили вершину B только с одной из вершин A, C, D или E, поэтому вершина C должна быть соединена с одной из оставшихся трех вершин: A, D или E.

Теперь учтем, что степень вершины D равна 2. Мы уже соединили вершины B и C с вершинами A, C, D или E, поэтому вершина D должна быть соединена только с одной из оставшихся двух вершин: A или E.

Теперь учтем, что степень вершины E равна 4. Мы уже соединили вершины B, C и D с вершинами A, C, D или E, поэтому вершина E должна быть соединена с последней оставшейся вершиной - A.

Теперь посчитаем сумму степеней всех вершин. Степень вершины A равна 4, степень вершины B равна 1, степень вершины C равна 3, степень вершины D равна 2 и степень вершины E равна 4. В сумме получаем 4 + 1 + 3 + 2 + 4 = 14.

Теперь посчитаем количество ребер. Мы соединили вершину B с одной из вершин A, C, D или E, вершину C соединили с одной из оставшихся трех вершин: A, D или E, вершину D соединили с одной из двух оставшихся вершин: A или E, и вершину E соединили с последней оставшейся вершиной - A. Итого получаем 4 ребра.

Теперь сравним сумму степеней и количество ребер: 14 ≠ 2 * 4.

Полученное равенство невыполнимо, что означает, что нельзя построить граф с пятью вершинами, у которого степени вершин равны 4, 1, 3, 2 и 4 без петель и кратных ребер.

б) Чтобы предоставить пример графа с пятью вершинами, где степени вершин равны 4, 1, 3, 2 и 4, можно нарисовать следующий граф:

\[
\begin{matrix}
&A &\underset{4}{\overset{}{\rightleftharpoons}}&E & \\
\underset{3}{\overset{}{\rightrightarrows}} &C & & &\underset{4}{\overset{}{\leftrightharpoons}} \\
& &\underset{1}{\overset{}{\rightleftharpoons}} &B & \\
\end{matrix}
\]

Здесь вершина A связана с вершинами C и E по 4 ребра, вершина C связана с вершиной B по 1 ребру, и вершина E связана с вершиной B по 3 ребрам.

Это пример графа, который удовлетворяет условию задачи.