Неориентированные графы

Доказать, что сумма степеней всех вершин произвольного неориентированного графа равна удвоенному количеству рёбер.

Доказать лемму «о рукопожатиях»: количество нечётных вершин в графе чётно.

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

Перечислить все неизоморфные неориентированные графы без петель, у которых не более четырёх вершин.

Мостом в связном графе называется ребро, при удалении которого граф перестаёт быть связным. Доказать, что ребро является мостом тогда и только тогда, когда оно не входит ни в какой простой цикл.

Доказать, что неориентированный связный граф с $n$ вершинами

Доказать, что во всякой группе $V$ из шести человек есть трое попарно знакомых или трое попарно незнакомых. Переформулировать указанную задачу в терминах графов.

Доказать, что неориентированный граф $\mathfrak {G}=(V, E)$ связен тогда и только тогда, когда для каждого разбиения $V=V_{1} \cup V_{2}$ с непустыми $V_{1}$ и $V_{2}$ существует ребро, соединяющее какую-то вершину из $V_{1}$ с какой-то вершиной из $V_{2}$.

Доказать, что если в неориентированном графе имеется ровно две нечётные вершины, то они связаны путём.

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

Пусть неориентированный граф без петель $\mathfrak {G}=(V, E)$ имеет $k$ компонент связности. Доказать, что тогда

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

Для геодезических исследований территорию триангулируют: разбивают на треугольные части. В вершинах треугольников устанавливают специальные знаки — вышки. Определить, сколько всего вышек потребуется для триангуляции, если территория разделена на $N$ треугольников, а на её границе располагается $K$ вышек.

Определить, сколько рёбер и вершин будет иметь многогранник, у которого $f$ граней и все они треугольные. Для каких $f$ такие многогранники могут существовать?

Исключением вершины называется такая операция с графом. Если есть вершина $v$ степени 2 с инцидентными рёбрами $(v, u)$ и $(v, w), u \neq w$, то мы удаляем вершину $v$ и инцидентные рёбра, а вместо них добавляем ребро $(u, w)$, рис. 41.

Рис. 41. Исключение вершины v.

Доказать, что при исключении вершин планарность и эйлеровость графа не меняются, а хроматическое число и гамильтоновость могут измениться.

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

Показать, что наличие в графе эйлерова и гамильтонова циклов друг от друга не зависит.

Определить, является ли следующий граф $\mathfrak {G}=(V, E)$ эйлеровым (полуэйлеровым). Если $\mathfrak {G}$ не является эйлеровым, то удалить из $\mathfrak {G}$ минимальное количество рёбер, чтобы он им стал. Построить в исходном или в получившемся графе эйлеров цикл. $V=\left\{ a, b, c, e, f, g, h, k, m, n\right\} , E=\left\{ (a, c),(a, h),(a, m),(a, k)\text{, }(b, c),(b, k),(b, f),(b, m),(c, k),(c, m),(e, f),(e, g),(f, k),(f, n),(g, m),(g, h)\text{, }(h, k),(h, m),(k, n)\right\}$.

Определить, является ли следующий граф $\mathfrak {G}=(V, E)$ двудольным. Если $\mathfrak {G}$ не двудольный, то удалить из $\mathfrak {G}$ наименьшее количество рёбер так, чтобы $\mathfrak {G}$ стал двудольным. $V=\left\{ a, b, c, e, f, g, h, k, m, n\right\} , E=\left\{ (a, h),(a, n),(a, k),(b, k),(b\text{, }f),(b, m),(c, k),(c, h),(e, f),(e, g),(f, a),(f, m),(g, m),(m, n)\right\}$.