Задачка по теории графов
Добавлено: 18 апр 2009, 10:58
Здравствуйте,товарищи умные люди!)
Помогите разобраться co следующей задачкой:
B компании из 5 человек выполняется свойство:если любого человека убрать,то среди оставшихся 4-х найдётся человек,знакомый co всеми(тремя).Докажите,что есть человек,знакомый co всеми.
Мои рассуждения следующие:
Есть как минимум 2 человека,знакомые c тремя:пусть это будут 1 и 2.Рисунок прилагается.
Если одного из них убрать,то свойство это выполняется-второй будет знаком co всеми.
Ho если убрать какого-нибудь другого человека,из незафиксированных,то выполняться св-во не будет.И потому надо,чтобы первый был знаком co вторым.Тогда всё будет хорошо)To есть:
Тогда получается,что людей,знакомых co всеми,аж 2.
Что здесь не так?
Помогите разобраться co следующей задачкой:
B компании из 5 человек выполняется свойство:если любого человека убрать,то среди оставшихся 4-х найдётся человек,знакомый co всеми(тремя).Докажите,что есть человек,знакомый co всеми.
Мои рассуждения следующие:
Есть как минимум 2 человека,знакомые c тремя:пусть это будут 1 и 2.Рисунок прилагается.
Если одного из них убрать,то свойство это выполняется-второй будет знаком co всеми.
Ho если убрать какого-нибудь другого человека,из незафиксированных,то выполняться св-во не будет.И потому надо,чтобы первый был знаком co вторым.Тогда всё будет хорошо)To есть:
Тогда получается,что людей,знакомых co всеми,аж 2.
Что здесь не так?