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

Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть?

В сказочной стране Перра-Терра среди прочих обитателей проживают Карабасы и Барабасы. Каждый Карабас знаком с шестью Карабасами и девятью Барабасами. Каждый Барабас знаком с десятью Карабасами и семью Барабасами. Кого в этой стране больше – Карабасов или Барабасов?

В турнире участвовали шесть шахматистов. Каждые два участника турнира сыграли между собой по одной партии. Сколько всего было сыграно партий? Сколько партий сыграл каждый участник? Сколько очков набрали шахматисты все вместе?

Можно ли нарисовать эту картинку (см. рис.), не отрывая карандаша от бумаги и проходя по каждой линии по одному разу? <img align="middle" src="/storage/problem-media/32095/problem_32095_img_1.jpg">

В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками.

Сколько человек в классе?

В графе из каждой вершины выходит по три ребра. Может ли в нём быть 1990 рёбер?

В графе каждая вершина – синяя или зелёная. При этом каждая синяя вершина связана с пятью синими и десятью зелёными, а каждая зелёная – с девятью синими и шестью зелёными. Каких вершин больше – синих или зелёных?

Могут ли степени вершин в графе быть равны:

  а) 8, 6, 5, 4, 4, 3, 2, 2?

  б) 7, 7, 6, 5, 4, 2, 2, 1?

  в) 6, 6, 6, 5, 5, 3, 2, 2?

На клетчатом листе закрасили 25 клеток. Может ли каждая из них иметь нечётное число закрашенных соседей?

Имеется 30 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечётное число знакомых, чётно.

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

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

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

  а) не с него начал и не на нём закончил?

  б) с него начал, но не на нём закончил?

  в) с него начал и на нём закончил?

В стране Семёрка 15 городов, каждый из которых соединён дорогами не менее, чем с семью другими.

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

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

Докажите, что число людей, когда-либо живших на Земле и сделавших нечётное число рукопожатий, чётно.

Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются семь островов, с каждого из которых ведет один, три или пять мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?

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

У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства одно, пять или девять соседних баронств?

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

В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?

В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединён ровно с пятью другими?

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

Между девятью планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер, Юпитер – Марс и Марс – Уран. Можно ли добраться с Земли до Марса?