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

Найти количество рёбер в $n$-вершинном неориентированном графе без петель, в котором любая пара различных вершин соединена ребром.

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

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

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

Может ли в государстве, в котором из каждого города выходит ровно пять дорог, быть ровно 77 дорог между городами? Может ли быть 80 дорог?

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

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

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

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

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

Привести пример, показывающий, что для пяти человек утверждение из предыдущей задачи может не выполняться.

Доказать, что во всяком графе $V$ из девяти вершин без петель есть четверо попарно соединённых или трое попарно не соединённых. Указание. Рассмотреть два случая:

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

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

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

Чему равно количество компонент связности неориентированного графа

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

Пусть $\mathfrak {G}=(V, E)$ — неориентированный граф. Представлением графа $\mathfrak {G}$ пересечениями называется пара $(A, f)$, где $A$ — произвольное множество, а $f: V \rightarrow \mathrm{P}(A)$ — разнозначная функция такая, что для любых различных вершин $u$ и $v$ множества $f(u)$ и $f(v)$ пересекаются тогда и только тогда, когда $(u, v) \in E$. Доказать, что для каждого графа такое представление существует.

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

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

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

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

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

Рис. 11: Исключение вершины 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),(b, c),(b, k),(b, f), (b, m),(c, k),(c, m),(e, f),(e, g),(f, k),(f, n),(g, m),(g, h),(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, f),(b, m),(c, k),(c, h),(e, f), (e, g),(f, a),(f, m),(g, m),(m, n)\right\}$.

Плоский граф $\mathfrak {G}$ с $n+1$ вершиной имеет вид правильного $n$-угольника, некоторые из вершин которого соединены с центром. Найти хроматическое число такого графа.