Zmenšení souvislého grafu
Úloha číslo: 4103
Ukažte, že:
Varianta
V každém souvislém grafu na \(n\ge 2\) vrcholech lze nalézt vrchol \(u\) takový, že graf \(G\setminus\{u\}\) je souvislý.
Nápověda
Při volbě uvažte možné vzdálenosti mezi vrcholy.
Řešení
Vrchol \(u\) zvolíme tak, že spolu s nějakým vrcholem \(w\) tvoří nejvzdálenější dvojici v \(G\), neboli jejich vzdálenost nabývá maxima.
Kdyby \(G\setminus\{u\}\) byl nesouvislý, potom by měl dvě komponenty, přičemž jedna by obsahovala \(w\) a druhá alespoň jeden vrchol, označme nějaký takový \(z\).
Každá cesta z \(w\) do \(z\) prochází skrz \(u\), tedy i délka nejkratší cesty mezi \(w\) a \(z\), je ostře větší než vzdálenost \(u\) a \(w\), což je ve sporu se způsobem jejich volby.
Varianta
V každém souvislém grafu na \(n\ge 3\) vrcholech lze nalézt dva vrcholy \(u\) a \(v\) takové, že všechny tři grafy \(G\setminus\{u\}\), \(G\setminus\{v\}\) a \(G\setminus\{u,v\}\) jsou souvislé.
Nápověda
Rozmyslete si nejprve, jaká má úloha řešení pro cykly a cesty.
Řešení
Nejprve zvolíme \(u\) postupem popsaným v předchozí variantě. Poté zvolíme vrchol \(v\) stejným způsobem ve (stále souvislém) grafu \(G\setminus\{u\}\). Stejným způsobem se zdůvodní, že graf \((G\setminus\{u\})\setminus\{v\}=G\setminus\{u,v\}\) je souvislý.
Zbývá ukázat, že i graf \(G\setminus\{v\}\) je souvislý. V tomto okamžiku je třeba se vrátit k předchozímu kroku a vybrat vrchol \(v\) tak, aby navíc pokud možno nesousedil s \(u\). Jen když to možné není, vybereme \(v\) jako prvek nejvzdálenější dvojice, i když sousedí s \(u\).
Nyní stačí rozebrat dva případy:
- Pokud \(u\) a \(v\) spolu nesousedí, potom má \(u\) v \(G\setminus\{v\}\) souseda \(w\), který je spojen se všemi ostatními vrcholy v \(G\setminus\{u,v\}\). Proto je v \(G\setminus\{v\}\) spojen se všemi ostatními vrcholy i vrchol \(u\), a to cestou přes \(w\).
- Pokud \(u\) a \(v\) spolu sousedí, pak \(u\) sousedí i s vrcholem \(w\), který je v grafu \(G\setminus\{u\}\) nejvzdálenější od \(v\). Stejně jako v předchozím bodě lze pak cesty z \(u\) vést přes \(w\).
Komentář
Postupná volba vrcholů vyplývá z potřeby ošetřit následující situace.
Kdybychom za \(u\) a \(v\) vzali nejvzdálenější dvojici vrcholů v \(G\), pak by důkaz selhal například na kružnici \(C_4\).
Kdybychom za \(v\) vzali z nejvzdálenější dvojice v \(G\setminus\{u\}\) souseda vrcholu \(u\), a přitom by druhý prvek dvojice s \(u\) nesousedil, pak by argument selhal například na cestě \(P_3\).
Varianta
Lze úlohu rozšířit i pro trojici vrcholů \(u,v,w\), aby všech 7 grafů, vzniklých odebráním libovolné podmnožiny této trojice bylo souvislých?Řešení
Ne, např. je-li daný graf cesta, pak v každé trojici vrcholů jeden separuje ostatní dva.
