Задачи по теории графов

[popkorn]

maxal писал(а):

popkorn
От противного - предположите, что из каждой вершины выходит как минимум 6 ребер, и получите отсюда противоречие с эйлеровой характеристикой.

Нет, ну то, что от противного - это понятно, но как? Ведь у нас нет формы клеток ("граней"), по сути, вообще ничего нет, кроме факта, что из каждой вершины выходит 6 или более рёбер.

[maxal]

Каждая грань содержит как минимум три ребра, а каждое ребро принадлежит двум граням. Отсюда следует, что число граней не превосходит $\frac{2}{3}m$, где $m$ - число ребер.

Для планарного графа с $n$ вершинами и $m$ ребрами из эйлеровой характеритики следует, что $n - m + \frac{2}{3}m \geq 2$ или $n-\frac{1}{3}m\geq 2.$ Понятно, что при $m\geq 3n$ это неравенство выполняться не может.

[popkorn]

maxal писал(а):

Каждая грань содержит как минимум три ребра, а каждое ребро принадлежит двум граням. Отсюда следует, что число граней не превосходит $\frac{2}{3}m$, где $m$ - число ребер.

Для планарного графа с $n$ вершинами и $m$ ребрами из эйлеровой характеритики следует, что $n - m + \frac{2}{3}m \geq 2$ или $n-\frac{1}{3}m\geq 2.$ Понятно, что при $m\geq 3n$ это неравенство выполняться не может.

Ага, понял, вот так, значит:

\[ \begin{gathered} 3\Gamma \leqslant 2{\rm P} \Rightarrow \Gamma \leqslant \frac{2} {3}{\rm P} \hfill \\ 6{\rm B} \leqslant 2{\rm P} \Rightarrow {\rm B} \leqslant \frac{1} {3}{\rm P} \hfill \\ {\rm B} - {\rm P} + \Gamma \leqslant 0 \hfill \\ \end{gathered} \]

Таким образом, приходим к противоречию с эйлеровой характеристикой. Спасибо )

[maxal]

popkorn писал(а):

maxal писал(а):

А вообще эту задачу можно усилить: 5 заменить на 4.
И, более того, для связного графа на $\geq 7$ вершинах 5 можно заменить на 3.

Это я не подумавши ляпнул, впрочем сразу же исправился.

[maxal]

Еще подсказки:

3) вспомните, когда в графе существует эйлеров цикл.

4) сначала раскрасьте двумя цветами как шахматную доску, а потом перекрасьте 8 удаленных друг от друга клеток в 8 оставшихся цветов

5) непонятное условие. по определению между двумя городами только одна дорога, как тогда из какого-то города можно проехать в другой по более чем двум (или даже одной) дорогам?

6) докажите индукцией по числу ребер в дереве