komplett bipartite graf

[kalleja]

har en oppgave der jeg skal vise at hvis m og n er større eller lik 3 så vil [tex]K_{m,n}[/tex], en komplett bipartite graf med V1=m, og V2=n, ha en hamilton cycle. der m og n er antall vertiser i denne grafen

Ser ikke helt denne etter de teoremene om hamilton cycler som står i boka mi, ta f.eks [tex]K_{5,3}[/tex] som eksempel, synes ikke det ser ut som denne har en hamilton cycle.

[Charlatan]

Du har rett. for hvert "steg" vi tar, vil vi nødvendigvis ende opp på det motsatte sett med vertiser. I settet vi begynner med, vil alltid antall vertiser besøkt være én mer, eller like mange antall vertiser besøkt i det andre settet. Siden 5 verken er lik, eller én mer enn 3, kan ikke [tex]K_{5,3}[/tex] ha en hamiltonsk syklus.