Grafer: Eulervägar och Hamiltoncykler

[@Skugen32]

Måste det vara två punkter med ojämnt gradtal för att det ska kunna finnas en eulerväg? Eller kan det vara 4 eller 6 noder med ojämnt gradtal? Har ett problem då det finns en graf med 10 noder med 9 gradtal per nod och frågan lyder om det finns en eulerväg eller krets, utan att man ska hitta vägen? Några tips/ regler man kan följa?

[@DanielCarlsson2]

Svaret finns i den senare delen av detta klipp där vi formulerar en sats för när det finns slutna eulervägar (alla gradtal jämna) respektive öppna eulervägar (precis två noder har udda grad). Noder med udda gradtal blir så småningom återvändsgränder, eftersom vi förbrukar två bågar varje gång vi besöker en nod, en på väg in och en ut. Har noden ett udda gradtal kommer vi efter några besök bara ha en väg in men ingen väg ut och fastna där. Har två noder udda grad kan den ena utgöra startnod i eulervägen och den andra slutnod för en öppen eulerväg.