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

[situs]

Тогда не думаю, что так проще. "Цикл длины больше 3" откуда появился?

[alcoholist]

Данное

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

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

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

явно уступает по ясности доказательству Geen

[situs]

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

явно уступает по ясности доказательству Geen

Это вопрос вкусов и предпочтений. К тому же не понятно откуда "циклы длины больше 3".
А допустим я использую это утверждение в работе не по теории графов. Тогда мне нужно дополнительно к понятию графа определять понятия "смежности, пути, цикла, дерева" ...

[arseniiv]

Зачем определять — они общеприняты, если речь о графах.

[alcoholist]

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

Предположим, наоборот, что <...>
Это действительно не так.

Если честно, то звучит коряво. Вроде бы от противного, а вроде бы и нет.

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

Тогда мне нужно дополнительно к понятию графа определять понятия "смежности, пути, цикла, дерева" ...

В вашей формулировке фигурируют куда более продвинутые понятия дву- и трехдольных графов.