Формулировка противоречия

[gogoshik]

Прошу, плиз, проверить формулировку противоречия.

Утверждение. Если граф $G$ не реализуем на торе, то он содержит один из подграфов $H_{1}, H_{2}, H_{3}$.
Предположим противное. Существуют графы нереализуемые на торе, не содержащие подграфы $H_{1}, H_{2}, H_{3}$.

Так можно?

[mihaild]

Да, а что вызывает сомнения?
(если под "не содержащие подграфы" понимается "не содержащие ни одного из подграфов")

[gogoshik]

Спасибо. Но я тут засомневался между:

(1) Существует граф не реализуемый на торе, не содержащий ни одного из подграфов $H_{1}, H_{2}, H_{3}$.
(2) Существуют графы не реализуемые на торе, не содержащие ни одного из подграфов $H_{1}, H_{2}, H_{3}$.

[Geen]

А где тут "противоречие"?

[Someone]

gogoshik в сообщении #1341137 писал(а):

Утверждение. Если граф $G$ не реализуем на торе, то он содержит один из подграфов $H_{1}, H_{2}, H_{3}$.

Тут некоторая неточность. Нужно говорить "содержит подграф, гомеоморфный одному из графов…". А в таком виде, как у Вас сформулировано, это утверждение неверно.

[gogoshik]

Спасибо. Поправил.

Утверждение. Если граф $G$ не реализуем на торе, то он содержит подграф, гомеоморфный одному из графов $H_{1}, H_{2}, H_{3}$.
Предположим противное, что существует граф не реализуемый на торе, не содержащий подграфа, гомеоморфного одному из графов $H_{1}, H_{2}, H_{3}$.

Так?

[Someone]

gogoshik в сообщении #1341143 писал(а):

Так?

Нет. Вы неправильно сформулировали отрицание утверждения.

[gogoshik]

Виноват. Предположим, что существует граф реализуемый на торе, содержащий подграф, гомеоморфный одному из графов $H_{1}, H_{2}, H_{3}$.

[george66]

Слово "существует" тут лишнее. Говорится про некоторый граф $G$, про его и надо говорить. И не "противоречие", а отрицание. Правильно так: предположим противное. Пусть граф $G$ не реализуем на торе, но не содержит ни один из подграфов $H_1,H_2,H_3$ (или гомеоморфных, тут я не берусь судить). Если бы утверждение было "всякий граф то-то и то-то", тогда отрицание начиналось бы со слова "существует".

[Munin]

gogoshik в сообщении #1341140 писал(а):

Спасибо. Но я тут засомневался между:

(1) Существует граф не реализуемый на торе, не содержащий ни одного из подграфов $H_{1}, H_{2}, H_{3}$.
(2) Существуют графы не реализуемые на торе, не содержащие ни одного из подграфов $H_{1}, H_{2}, H_{3}$.

В принципе, со всей строгостью надо выбирать вариант (1). Но поскольку мы знаем, что имея один граф искомого вида, можно легко получить хотя бы ещё несколько, то разницы нет. Кроме того, вряд ли вы где-то в доказательстве будете использовать множественное число, так что формулировка (2) превращается просто в словесное украшение.