Совершенное паросочетание в регулярном графе

[Alexander Evnin]

Пусть в графе $4n$ вершин и степень каждой вершины равна $2n-1$. Обязательно ли в таком графе существует совершенное паросочетание?
Если степень каждой вершины $2n$, то, по теореме Дирака, граф гамильтонов и в нём существуют по меньшей мере два совершенных паросочетания без общих рёбер. Если же степень уменьшить на единицу, то гамильтоновость уже не гарантирована, но, может быть, гарантировано существование совершенного паросочетания?

[sqribner48]

Alexander Evnin.
Для начала попробуйте поэкспериментировать - построить графы, удовлетворяющие заданным условиям, для разных $n$. Так для $n=1$ получим цикл с 4 вершинами. Степень каждой вершины равна $2 \cdot 1 -1=1$. Этот граф имеет совершенное паросочетание. Потом можно построить граф для $n=2$. Это куб с 8 вершинами, степень каждой вершины равна $2 \cdot 2 - 1=3$. И этот граф имеет совершенное паросочетание. И так далее...
А вообще вспомните, что совершенное паросочетание графа есть 1-фактор. Далее можно попробовать использовать теорему 9.4 об 1-факторе из книги Ф. Харари. Теория графов...

[Alexander Evnin]

sqribner48 Для начала хочу заметить, что, при $n=1$ имеем вовсе не цикл, а при $n=2$, кроме куба, довольно много есть кубических графов с 8 вершинами. Даже в этом случае перебор возможных вариантов довольно кропотлив. Что уж говорить о так далее... Не думаю, что здесь поможет рассуждение по индукции.
Как использовать теорему, на которую Вы ссылаетесь, совершенно неясно!
Впрочем, буквально на днях задачу эту я решил. Ответ положительный!

[sqribner48]

Alexander Evnin
Рад за Вас, что удалось найти решение.

Alexander Evnin в сообщении #972108 писал(а):

sqribner48 Для начала хочу заметить, что,...

А зачем придираться к словам? Я что, Вас обидел? Я просто хотел дать какую-то исходную "зацепку" для вашей мысли, поскольку правилами форума запрещается сразу давать готовое решение... С циклом я допустил ошибку.
А почему Вы не сделали сообщение, что задача уже решена? Обычно большинство участников форума пишут об этом, из уважения к другим участникам форума (для экономии их времени).

Alexander Evnin в сообщении #972108 писал(а):

при $n=2$, кроме куба, довольно много есть кубических графов с 8 вершинами. Даже в этом случае перебор возможных вариантов довольно кропотлив.

Похоже я не правильно понял задачу. Я подумал, что для любого $n$ надо найти хоть один граф с совершенным паросочетанием.

Alexander Evnin в сообщении #972108 писал(а):

Не думаю, что здесь поможет рассуждение по индукции.

А интересно, как можно решить эту задачу для любого $n$ без применения метода математической индукции?

[provincialka]

sqribner48
Вообще-то это олимпиадный раздел, а не ПРР. Поэтому часто дают решенные задачи.
Кроме того, посмотрите на даты сообщений.

[sqribner48]

provincialka
Дата 08.01.2015 вроде не очень древняя? А какой срок принято считать древним?

[provincialka]

В данном контексте - почти любой. Если 8.01 человек не знал решение, то к 01.02 - уже решил ("на днях" написано). По-вашему, он должен был сразу всех оповестит?
Да это и не важно, в олимпиадном разделе вполне нормально помещать уже решенные задачи, для любителей поломать голову.

Впрочем, думаю, мне не стоит говорить за Alexander Evnin .

[Alexander Evnin]

sqribner48 Если это так Вам интересно, задачу я решил 30.01.2015.

Цитата:

Я подумал, что для любого $n$ надо найти хоть один граф с совершенным паросочетанием

Тогда бы никакой задачи не было!:)

Цитата:

А интересно, как можно решить эту задачу для любого $n$ без применения метода математической индукции?

Я взял максимальное (по мощности) паросочетание, а потом показал, что он совершенное. При этом, рассуждая от противного, использовал увеличивающие цепи длины 3 и 5.

[sqribner48]

Alexander Evnin
Спасибо. Это (решение) интересно.

(Оффтоп)

Насчет моего вопроса про дату. Мне показалось, что это задача из ПРР. А там довольно жестко контролируется "свежесть" последнего сообщения в посте. Поэтому, чтобы в дальнейшем не попадать впросак, я и спросил об этом.