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

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

У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными.

Сколько потомков было у царя Гвидона?

В стране <i>n</i> городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.

Доказать, что в двудольном плоском графе  <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 дорог.

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

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

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

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

Каждое из рёбер полного графа с 6 вершинами покрашено в один из двух цветов.

Докажите, что есть три вершины, все рёбра между которыми – одного цвета.

На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.

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

Докажите, что для плоского графа справедливо неравенство  2<i>E</i> ≥ 3<i>F</i>.

Пусть связный плоский граф с <i>V</i> вершинами и <i>E</i> рёбрами разрезает плоскость на <i>F</i> кусков. Докажите формулу Эйлера:  <i>V – E + F</i> = 2.

В стране из каждого города выходит 100 дорог и от каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт.

Докажите, что и теперь от каждого города можно добраться до любого другого.

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