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

[Geen]

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

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

Либо звезда, либо треугольник.

[situs]

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

Либо звезда, либо треугольник.

Вы говорите про такое: если в графе любые два ребра имеют общую вершину, то граф либо звезда, либо треугольник?

[alcoholist]

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

если в графе любые два ребра имеют общую вершину, то граф либо звезда, либо треугольник

Вероятно, да. Ну и обратное тоже верно.

[situs]

alcoholist в сообщении #1383702 писал(а):

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

если в графе любые два ребра имеют общую вершину, то граф либо звезда, либо треугольник

Вероятно, да. Ну и обратное тоже верно.

Хорошо. А как из этого следует, что граф является объединением изолированных вершин и полного дву- или трехдольного графа.

[Geen]

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

Вы говорите про такое: если в графе любые два ребра имеют общую вершину, то граф либо звезда, либо треугольник?

Нет, я говорю про то, что звезда и треугольник не содержат $G_1$, а любой другой - содержит (не считая изолированных вершин).

[Sender]

Ну и звезда - полный двудольный граф, а треугольник - полный трёхдольный, если на то пошло.

[situs]

Это так! Спасибо! А как получили условие "любые два ребра имеют общую вершину" на которое указал arseniiv и для чего оно нужно?

[Sender]

Ну а вы посмотрите внимательнее на граф $G_1.$ При каком условии он может содержаться в исходном графе?

[situs]

Исходный граф - это какой? При условии "любые два ребра имеют общую вершину" получается полный дву- или трехдольный граф.

Я никак не пойму, простите. Мне предложили, если я правильно всё понял, переформулировать утверждение так: если граф не содержит $G_1$, тогда граф является объединением изолированных вершин и полного дву- или трехдольного графа. Не пойму, какой следующий шаг.

[arseniiv]

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

Зачем переформулировать условие? Как это поможет доказательству?

Ну, это может немного убыстрить тот перебор, который вы делали: сразу видно, что к графу $K_{1,2}$ можно добавить ребро особым способом, который даёт уже нерасширяемый граф $C_3\equiv K_{1,1,1}$, а остальные $K_{1,n}$ можно расширять только до $K_{1,n+1}$ (с точностью до добавления изолированных вершин, конечно). По идее когнитивно меньше нагрузки проверять конкретную вещь — добавление ребра так, чтобы оно имело с каждым общую вершину, чем проверять невхождение подграфа (в вашем исходном случае ещё и четырёх!).

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

Задача поставлена в том виде, который я изначально привел.

Хм, странно, потому что правда же условие избыточно, а следствие слишком общее. Я сперва подумал, что вы её вытащили из какой-то практической задачи, и потому она вышла поначалу такая непричёсанная.

-- Вс мар 24, 2019 17:00:18 --

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

Не пойму, какой следующий шаг.

Хм, шаг… ну всё же можно оставить как было, если вас устраивает исходная формулировка.

Вот вы хотели разобраться почему «не содержит $G_1$» эквивалентно «любые два ребра имеют общую вершину» — тут по крайней мере понятнее чем можно помочь: попробуйте с отрицаниями — «содержит $G_1$» должно быть эквивалентно «не любые два ребра имеют общую вершину», т. е. «существуют два ребра, не имеющие общих вершин». Это ведь как раз вложимость $G_1$ и есть. В крайнем случае можно формально записать и это, и утверждение о подграфе, и попытаться преобразовать их к одному.

[situs]

Вот все равно ничего не понял.

Давайте еще раз.

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

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

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

Только как этот факт аккуратно выразить в тексте?

[arseniiv]

Ну примерно так и сформулировать. (Я чего-то не понимаю.) Ну вот индукцию например можно делать по числу рёбер, а число вершин пусть будет заранее произвольное и база индукции — граф из изолированных вершин.

[Geen]

Зачем вообще индукция - граф либо имеет цикл, либо не имеет его. Если цикл длины больше 3, то можно найти два несмежных ребра. Если в дереве есть путь длины больше 2, то можно найти два несмежных ребра.
Что я упускаю?...

[situs]

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

Зачем вообще индукция - граф либо имеет цикл, либо не имеет его. Если цикл длины больше 3, то можно найти два несмежных ребра. Если в дереве есть путь длины больше 2, то можно найти два несмежных ребра.
Что я упускаю?...

Geen
Что то я упустил. Скажите, пожалуйста, какое утверждение Вы доказываете этим способом?

[Geen]

Исходное