Олимпиадные задачи из источника «глава 5. Графы» для 6 класса - сложность 2 с решениями

Доказать, что в двудольном плоском графе  <i>E</i> ≥ 2<i>F</i>,  если  <i>E</i> ≥ 2  (<i>E</i> – число рёбер, <i>F</i> – число областей).

Доказать, что

  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;

  б) в дереве с <i>n</i> вершинами ровно  <i>n</i> – 1  ребро;

  в) в дереве не меньше двух висячих вершин;

  г) в связном графа из <i>n</i> вершин не меньше  <i>n</i> – 1  ребра;

  д) если в связном графе <i>n</i> вершин и  <i>n</i> – 1  ребро, то он – дерево.

а) Из какого минимального числа кусков проволоки можно спаять каркас куба?

б) Какой максимальной длины кусок проволоки можно вырезать из этого каркаса? (Длина ребра куба равна 1 см.)

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

Существует ли ломаная, пересекающая все рёбра картинки по одному разу? <div align="center"><img width="68" height="26" align="BOTTOM" border="0" src="/storage/problem-media/31093/problem_31093_img_2.gif"></div>

Можно ли начертить, не отрывая карандаша от бумаги (одним росчерком)

  а) квадрат с диагоналями?

  б) шестиугольник со всеми диагоналями?

В стране каждые два города соединены дорогой с односторонним движением.

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

Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.

Доказать, что число штатов США с нечётным числом соседей чётно.

Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза.

Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.

В графе 100 вершин, причём степень каждой из них не меньше 50. Доказать, что граф связен.

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

В некоторой стране из столицы выходит 89 дорог, из города Дальний – одна дорога, из остальных 1988 городов – по 20 дорог.

Доказать, что из столицы можно проехать в Дальний.

В кружке у каждого члена имеется один друг и один враг. Доказать, что

  а) число членов чётно.

  б) кружок можно разделить на два нейтральных кружка.

Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.