matematikk.net

Hvor mange forskjellige sammenkoblede grafer (opp til isomorfi) av minimal størrelse (minimalt antall kanter) med n noder slik at hver node har en maksimal grad 4 eksisterer?

Oppgaven er altså å finne en formel for hvor mange ulike (opp til isomorfi) spenntrær slik at hver node har maksimal grad 4 som finnes.

To grafer G og H er like opp til isomorfi dersom det finnes en bijeksjon f fra nodene til G til nodene til H slik at det er en kant mellom nodene u og v i G hvis og bare hvis det er en kant mellom nodene f(u) og f(v) i H.

Hva betyr det at enhver node har en maksimal grad 4? At alle noder har grad fire, eller at ingen har grad større enn fire eller noe annet?

Jeg mente at nodene ikke kan ha grad større enn 4 ja. I og med at det er et spenntre det er snakk om må minst 2 noder ha grad 1 uansett.