Графы (одно доказательство)

[situs]

Доброго времени суток!

Доказываю следующее утверждение: если граф не содержит ни одного из графов $G_1, G_2, G_3, G_4$ (см. рисунок, верхний ряд), то граф является объединением изолированных вершин и полного дву- или трехдольного графа.

Доказательство от противного. Предположим, что существует граф который не является объединением изолированных вершин и полного дву- или трехдольного графа и не содержит ни одного из графов $G_1, G_2, G_3, G_4$.

Далее я показываю (на рисунке под первым рядом), что такого не может быть (см. рисунок). Начинаю рассматривать с минимального графа, то есть с одной вершины (изолированной) и далее добавляю вершины и ребра. В итоге получается, что это либо дву- или трехдольный граф с изолированными вершинами (множество изолированных вершин может быть пустое), либо граф содержащий один из $G_1, G_2, G_3, G_4$.

Посмотрите, пожалуйста. Это же индукция. Хотел бы узнать, как более строго оформить доказательство?

[Geen]

situs в сообщении #1383625 писал(а):

не содержит ни одного из графов $G_1, G_2, G_3, G_4$

А одного графа разве не достаточно?

[situs]

Geen в сообщении #1383627 писал(а):

situs в сообщении #1383625 писал(а):

не содержит ни одного из графов $G_1, G_2, G_3, G_4$

А одного графа разве не достаточно?

Это Вы про $G_3$? Думаю, что не достаточно.

[arseniiv]

Видимо, про $G_1$ — он содержится в $G_2, G_3, G_4$, так что если в графе не содержится $G_1$, в нём не содержатся и остальные, и тривиально, что если в графе не содержится ни один из них, в нём не содержится и $G_1$, так что условия не содержать $G_1$ и не содержать все четыре эквивалентны.

-- Сб мар 23, 2019 02:06:57 --

Дальше условие переформулируется в «любые два ребра имеют общую вершину», после чего путей добавления рёбер действительно мало, а следствие теоремы можно усилить. (Но достаточно уже и того, что есть?)

[situs]

arseniiv

Действительно. Спасибо! Правда вторую часть (добавленное Вами сообщение) я не совсем понял. Зачем переформулировать условие? Как это поможет доказательству? Задача поставлена в том виде, который я изначально привел.

[Geen]

situs в сообщении #1383625 писал(а):

Это же индукция.

А что по поводу $K_{2,2}$?

[situs]

Geen в сообщении #1383638 писал(а):

situs в сообщении #1383625 писал(а):

Это же индукция.

А что по поводу $K_{2,2}$?

А что с ним не то исходя из

situs в сообщении #1383625 писал(а):

Предположим, что существует граф который не является объединением изолированных вершин и полного дву- или трехдольного графа и не содержит $G_1$

[Geen]

situs в сообщении #1383643 писал(а):

А что с ним не то

Так он содержит или нет?

[situs]

Geen в сообщении #1383646 писал(а):

situs в сообщении #1383643 писал(а):

А что с ним не то

Так он содержит или нет?

Он содержит. Так и должно быть.

[Geen]

situs в сообщении #1383648 писал(а):

Он содержит. Так и должно быть.

Да, спасибо, я просто в порядке уточнения спрашивал - просто Ваша формулировка "теоремы" не очень нравится...

[situs]

Так что же с индукцией? Как более аккуратно оформить доказательство утверждения?

[Geen]

situs в сообщении #1383652 писал(а):

Как более аккуратно оформить доказательство утверждения?

Не знаю - мне кажется, что в данном случае более строгое утверждение проще доказать

[situs]

Какое более строгое утверждение?

[situs]

arseniiv в сообщении #1383632 писал(а):

Дальше условие переформулируется в «любые два ребра имеют общую вершину», после чего путей добавления рёбер действительно мало, а следствие теоремы можно усилить. (Но достаточно уже и того, что есть?)

Вот чего-то я не понимаю. Может быть "любые два соседних ребра имеют общую вершину"? Переформулируем условие как Вы предлагаете: если в графе любые два ребра имеют общую вершину, тогда он является объединением изолированных вершин и полного ... Что-то не так!

[alcoholist]

situs в сообщении #1383663 писал(а):

"любые два соседних ребра имеют общую вершину"

это тавтология