matematikk.net

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.

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.