Grafteori

[Charlatan]

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.

[Karl_Erik]

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?

[Charlatan]

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.