WisFaq!

De graad van een vertex in een outerplanar graaf

Gegeven is een outerplanar graaf. Te bewijzen is dat er een vertex bestaat in de graaf met graad hoogstens 2. Ik heb een bewijs gevonden dat een deel van de graaf bekijkt zonder kanten die volledig in een inner-regio liggen (inner face). Echter snap ik niet hoe we dan direct concluderen dat de graad van een vertex hoogstens 2 is.

Het bewijs:
Choose an arbitrary interior edge. Since it connects two points on the exterior of the graph, it divides the graph into two parts. Choose one of the parts. Pick an interior edge in that part. It divides the graph again. Pick the part that does not contain the first edge. Keep going in this way, always picking the part not containing your previously chosen edges. As there are only finitely many edges, eventually this has to stop - there are no more interior edges on one side of your final pick. But since faces with two edges only are not allowed, the face on that side has to have at least one more vertex. Any such vertex cannot have an interior edge connecting to it, so it can only have the two exterior edges. I.e., its degree is 2. (https://math.stackexchange.com/questions/2781157/two-questions-about-outerplanar-graph-while-working-on-a-3-color-problem-of-the)

Richard
4-3-2022

Antwoord

Het antwoord is onvolledig: de overgebleven graaf, inclusief die laatste lijn, heeft inderdaad geen `inner edges' meer maar hoeft niet uit een `face' te bestaan; er kunnen nog extra lijnen uit de punten vertrekken en er kunnen nog meer faces zijn.
Hier is een ander argument: neem aan dat je graaf samenhangend is (neem andere een component van je graaf) en niet flauw is, met tenminste vier punten.
Bij drie punten of minder heb je zeker een punt met graad $1$ of $2$.
Neem twee punten $u$ en $v$ met maximale afstand: het kortste pad tussen $u$ en $v$ is het langste van alle kortste paden tussen paren punten.
Bewering $u$ en $v$ hebben graad $2$.
Stel $u$ heeft drie of meer buren, zeg $w_1$, $w_2$, en $w_3$.
Het kortste pad $P_i$ van $w_i$ naar $v$ loopt niet door $u$ (want dan zou het $1$ langer zijn dan het kortste pad van $u$ naar $v$.
Zo krijgen we drie paden van $u$ naar $v$: telkens van $u$ naar $w_i$ en dan $P_i$ volgen. Die paden komen bij elkaar bij $v$ of eerder, misschien al meteen na de $w_i$. Teken een plaatje van zo'n situatie: er zal altijd een $i$ zijn zo dat $w_i$ binnen de cykel gevormd door de paden via de andere twee $w$s.
Maar dan zou $G$ niet outerplanair zijn: die $w_i$ is van buiten niet te zien.

kphart
5-3-2022