k-regulární hranově (k-2)-souvislý graf

Úloha číslo: 3271

Pro každé \(k\ge 3\) nalezněte \(k\)-regulární hranově \((k-2)\)-souvislý graf na sudém počtu vrcholů, který nemá perfektní párování.

  • Nápověda

    Zkonstruujte lichou komponentu a množinu \(S\) tak, aby bylo patrné, že výsledný graf porušuje Tutteho podmínku.

  • Řešení

    Pro sudé \(k\) vytvoříme lichou komponentu z \(K_{k+1}\) tak, že vybereme párování o \(\frac{k-2}{2}\) hranách, a tyto hrany odstraníme. Označme tento graf \(K’\).

    Vezmeme celkem \(k\) kopií \(K’\) a k nim přidáme \(k-2\) nových vrcholů tvořících množinu \(S\). Tyto části propojíme tak, aby každý vrchol \(S\) sousedil s jedním vrcholem z každé kopie \(K’\) a aby výsledný graf byl \(k\)-regulární. Jinými slovy, hrany mezi \(S\) a každou kopií \(K’\) tvoří perfektní párování mezi \(S\) a vrcholy stupně \(k-1\) v \(K’\).

    Po odebrání množiny \(S\) z výsledného grafu \(G\) máme \(|S+2|\) lichých komponent, a proto \(G\) porušuje Tutteho podmínku a nemá perfektní párování.

    Zbývá ukázat, že odebereme-li libovolných \(k-3\) hran z \(G\), zůstane graf souvislý. Každá kopie \(K’\) bude mít vrchol spojený s ostatními, tedy je souvislá. Z každého vrcholu \(S\) vede alespoň jedna hrana do některé kopie \(K’\). Podle Dirichletova principu u alespoň jednoho vrcholu \(S\) zůstanou hrany do všech kopií \(K’\), tedy výsledný graf je souvislý.

    Pro liché \(k\) postupujeme stejným způsobem, jen konstrukce \(K’\) je o krok složitější. Stejně jako v předchozím případě z \(K_{k+1}\) vybereme párování o \(\frac{k-3}{2}\) hranách, a tyto hrany odstraníme. Dále zvolíme ještě jedno párování o \(\frac{k-1}{2}\) hranách. Každou hranu tohoto párování podrozdělíme jedním novým vrcholem. Těchto \(\frac{k-1}{2}\) vrcholů sloučíme do jednoho, čímž vznikne \((k-2)\)-hý neboli poslední potřebný vrchol stupně \(k-1\).

    Zbývá ověřit, že výsledný graf \(K’\) je skutečně dosti souvislý. Pomocí Mengerových vět lze ukázat, že přidání jednoho vrcholu, který vzikne identifikací vrcholů podrozdělených hran se \((k-2)\)-souvislost zachová.

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze