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

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

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

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

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

Несколько шестиклассников и семиклассников обменялись рукопожатиями. При этом оказалось, что каждый шестиклассник пожал руку семи семиклассникам, а каждый семиклассник пожал руку шести шестиклассникам. Кого было больше - шестиклассников или семиклассников?

На сторонах некоторого многоугольника расставлены стрелки.

Докажите, что число вершин, в которые входят две стрелки, равно числу вершин, из которых выходят две стрелки.

Художник-авангардист нарисовал картину "Контур квадрата и его диагонали".

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

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

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

Выписать в ряд цифры от 1 до 9 (каждую по разу) так, чтобы каждые две подряд идущие цифры давали бы двузначное число, делящееся на 7 или на 13.

Гуляя по Кенигсбергу, Леонард Эйлер захотел обойти город, пройдя по каждому мосту ровно один раз (см. рис.). Как ему это сделать? <div align="center"><img src="/storage/problem-media/32993/problem_32993_img_2.gif"></div>

Можно ли расположить на плоскости

  а) 4 точки так, чтобы каждая из них была соединена отрезками с тремя другими (без пересечений)?

  б) 6 точек и соединить их непересекающимися отрезками так, чтобы из каждой точки выходило ровно 4 отрезка?

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

Страна называется <i>пятёрочной</i>, если в ней каждый город соединён авиалиниями ровно с пятью другими городами (международных рейсов нет).

  а) Нарисуйте схему авиалиний для пятёрочной страны из 10 городов.

  б) Сколько авиалиний в пятёрочной стране из 50 городов?

  в) Может ли существовать пятёрочная страна, в которой ровно 46 авиалиний?

В поселке 20 жительниц. 1 марта одна из них узнала интересную новость и сообщила её всем своим подругам. 2 марта те сообщили новость всем своим подругам, и так далее. Может ли так случиться, что:

  а) 15 марта ещё не все жительницы будут знать новость, а 18 марта уже все?

  б) 25 марта ещё не все жительницы будут знать новость, а 28 марта уже все?

Можно ли нарисовать эту картинку (см. рис.), не отрывая карандаша от бумаги и проходя по каждой линии по одному разу? <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 человек, некоторые из них знакомы. Доказать, что число человек, имеющих нечётное число знакомых, чётно.

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

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

Докажите, что в дереве каждые две вершины соединены ровно одним простым путем.