Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

 Dit is een reactie op vraag 62870 

Re: Enkelvoudige grafen

Dit is niet goed. Er zijn 4 niet-isomorfe grafen met deze valentierij.

Groet, Anneke

Anneke
Beantwoorder - dinsdag 25 september 2018

Antwoord

Dit klopt, bedankt.

Voor de volledigheid: in het oorspronkelijke antwoord werd er te snel vanuit gegaan dat er een rondwandeling van lengte $6$ zou moeten zijn, daardoor werden twee mogelijkheden, namelijk II en IV, gemist.

Ook voor de volledigheid: je kunt de vier grafen hierboven vinden door systematisch te kijken hoe de buren vanuit het punt van graad $4$ verdeeld en verbonden zijn. Er zijn twee mogelijkheden voor de verdeling van de graden: $(2,2,2,3)$ en $(2,2,3,3)$.

Geval $(2,2,2,3)$ en een losse $3$: je kunt geen $2$-en verbinden want dan kan het losse punt met graad $3$ nog maar twee buren hebben. Als je een $2$ en een $3$ verbindt kom je uit op plaatje IV.

Dit is het enige geval: er gaan vier lijnen vanuit $4$ en drie vanuit de losse $3$, er is dus nog maar één lijn over om tussen de buren van $4$ te trekken.

Geval $(2,2,3,3)$ met nog een losse $2$: je kunt de $2$-en verbinden; dan moet je de $3$-en verbinden en die moeten ook met de losse $2$ verbonden worden, dat is plaatje II; je kunt tweemaal een $2$ en een $3$ verbinden dan moeten de $3$-en weer aan de losse $2$ (plaatje I); ten slotte verbind je de $3$-en en een $2$ met een $3$, dan moet de losse $2$ aan de andere $2$ en de andere $3$ verbonden worden (plaatje III).

Dit zijn alle gevallen want naast de vier lijnen vanuit het punt met graad $4$ en de twee vanuit het losse punt van graad $2$ zijn er twee lijnen over om tussen de buren van $4$ te trekken.

kphart
vrijdag 5 oktober 2018

©2001-2024 WisFaq