Существует ли двудольный граф, в котором 18 вершин, причем 7 имеют степень 3, десять вершин имеют степень 6 и одна вершина степени 7?

задан 7 Окт '15 21:28

10|600 символов нужно символов осталось
3

Нет, не существует.

Чтобы убедиться, сосчитаем сумму всех степеней - то есть удвоенное число ребер. Сумма равна $%7\cdot3+6\cdot10+1\cdot7=88$%. Значит, всего 44 ребра. Но так как на обе доли есть всего одна вершина, степень которой не кратна 3, то в какой-то из долей все вершины имеют степень 3 или 6, а значит, число ребер (исходящих наружу из этой доли) должно быть числом, кратным 3. Противоречие (44 не кратно 3) доказывает, что такого графа не существует.

ссылка

отвечен 7 Окт '15 21:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×481

задан
7 Окт '15 21:28

показан
913 раз

обновлен
7 Окт '15 21:56

Отслеживать вопрос

по почте:

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

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru