WisFaq!

Re: De graad van een vertex in een outerplanar graaf

Bedankt voor uw antwoord. Prachtig bewijs. Stel dat er een lijn is van w1 naar w2, en een lijn van w2 naar w3. Stel nu dat het kortste pad van w1 naar v via w2 en dan w3 gaat. Stel nu ook dat het kortste pad van w2 naar v via w3 gaat. Stel verder dat het kortste pad van w3 naar v niet via de andere w’s gaat. Dan hebben we geen cykel waarin een w ‘opgesloten’ zit. Hoe lossen we dit randgeval op?

Richard
5-3-2022

Antwoord

Het geval dat het kortste pad van $w_1$ naar $v$ via $w_2$ en $w_3$ gaat doet zich niet voor: dan is dat kortste pad $1$ langer dan het het pad dat je krijgt door van $u$ naar $w_3$ te gaan en dat het pad vanuit $w_1$ te volgen.
Maar het zou toch mogelijk zijn dat de kortste paden vanuit $w_1$ en $w_3$ (ook) via $w_2$ lopen.

Daarom moeten we he bewijs toch iets aanpassen: volg het bewijs van mathoverflow tot we een graaf zonder inner edges hebben, en neem aan dat die samenhangend is. Bekijk de laatste inner edge, zeg $\{a,b\}$.
Neem vanuit elk ander punt het kortste pad naar $a$, en neem het punt $u$ waarvoor dit punt het langst is, en neem aan dat die drie buren $w_1$, $w_2$, en $w_3$ heeft.
Als nu, bijvoorbeeld, $w_2$ met $w_1$ en $w_3$ verbonden is dan is $\{u,w_2\}$ een inner edge binnen het cykel $\{u,w_1,w_2,w_3\}$, maar dat kan niet.
Er is dus ten hoogste één verbinding tussen de buren. Als die er niet is zijn we klaar, als in het vorige antwoord.
Als, bijvoorbeeld, $\{w_2,w_3\}$ een verbinding is en het kortste pad van beide naar $a$ loopt via $w_2$ dan loopt er geen ander pad van $w_3$ naar $a$, anders krijgen we dezelfde tegenspraak als in het vorige antwoord.
Dus als $v$ een andere buur van $w_3$ is loopt het kortste pad van $v$ naar $a$ via $w_3$, maar dan is het $1$ langer dan het kortste pad van $w_3$ naar $a$ en dus ook $1$ langer dan het kortste pad van $u$ naar $a$, tegenspraak. Conclusie: $w_3$ heeft alleen $u$ en $w_2$ als buren en heeft dus graad $2$.

kphart
6-3-2022