Расширение 3-связных графов дает 3-связные графы - Математика
Купить гитару в Москве
1 голос
/

Итак, я работаю над проблемой теории графов, которая гласит: Расширение графа $G$ формируется путем деления двух ребер на $G$ (подразделение ребра $vw$ означает замену $vw$ на путь $vxw$ через новую вершину $x)$) и добавление ребра между этими двумя новыми вершинами. Докажите, что если $G$ является 3-связным, то любое расширение $G$ также является 3-связным. Получить граф Петерсона из $K_4$ путем повторных разложений.

Теперь я смог получить граф Петерсона, так что с частью все в порядке. Для доказательства я думал, что у меня есть $G$, который является 3-связным, и я получаю $G’$, расширяя $G$ (скажем, у меня были ребра $xy$ и $wz$, и я разделил их, чтобы получить $xsy$ и $wtz$ и край $st$). Чтобы доказать, что $G’$ является 3-связным, я хочу показать, что, если я удаляю вершину из $G’$, я получаю 2-связный граф и, таким образом, декомпозицию уха. Если вершина $v$, которую я удаляю, не является $s$ или $t$, то разложение уха для $G-v$ должно как-то дать мне значение $G’-v$, и тогда я не знаю, что делать с $G’-v$когда $v$ равно $s$ или $t$.

Кроме того, есть ли способ сделать это, используя теорему Менгера о внутренне непересекающихся путях?

Добро пожаловать на сайт Математика, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...