Back to Browse

What is...the difference between Eulerian and Hamiltonian graphs?

15.8K views
Sep 25, 2021
16:42

Goal. I would like to tell you a bit about my favorite theorems, ideas or concepts in mathematics and why I like them so much. This time. What is...the difference between Eulerian and Hamiltonian graphs? Or: They are not dual!? Disclaimer. Nobody is perfect, and I might have said something silly. If there is any doubt, then please check the references. Slides. http://www.dtubbenhauer.com/youtube.html Thumbnail. https://en.wikipedia.org/wiki/Hypercube#/media/File:Hypercube.svg Eulerian and Hamiltonian graphs. https://en.wikipedia.org/wiki/Eulerian_path https://en.wikipedia.org/wiki/Hamiltonian_path https://en.wikipedia.org/wiki/Hamiltonian_path_problem https://ulsites.ul.ie/cemtl/sites/default/files/cemtl_graph_euler_hamilton.pdf https://stackoverflow.com/questions/3269013/difference-between-hamiltonian-path-and-euler-path https://math.stackexchange.com/questions/667978/association-between-hamiltonian-and-eulerian-graphs Line graph and Euler vs. Hamilton. https://en.wikipedia.org/wiki/Line_graph https://math.stackexchange.com/questions/2175193/g-is-eulerian-if-and-only-if-lg-has-a-hamiltonian-cycle (Non-)Eulerian and (non-)Hamiltonian. https://math.stackexchange.com/questions/1113613/probability-of-choosing-a-graph-with-hamiltonian-cycle http://oeis.org/A003049 http://oeis.org/A003216 https://mathworld.wolfram.com/NoneulerianGraph.html http://oeis.org/A158007 https://mathworld.wolfram.com/NonhamiltonianGraph.html http://oeis.org/A246446 Number of connected graphs. http://oeis.org/A001349 Bondy-Chvátal and co. https://en.wikipedia.org/wiki/Hamiltonian_path#Bondy%E2%80%93Chv%C3%A1tal_theorem https://en.wikipedia.org/wiki/Ore%27s_theorem https://www.theoremoftheday.org/CombinatorialTheory/Ore/TotDOre.pdf https://proofwiki.org/wiki/Ore%27s_Theorem Bridges in Königsberg. https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg https://www.maa.org/press/periodicals/convergence/leonard-eulers-solution-to-the-konigsberg-bridge-problem https://mathworld.wolfram.com/KoenigsbergBridgeProblem.html https://math.stackexchange.com/questions/1173328/eulers-solution-of-seven-bridges-of-k%C3%B6nigsberg-in-layman-terms Mathematica. https://reference.wolfram.com/language/ref/FindEulerianCycle.html https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html https://reference.wolfram.com/language/ref/LineGraph.html https://reference.wolfram.com/language/ref/GraphData.html https://demonstrations.wolfram.com/TheSevenBridgesOfKoenigsberg/ Pictures used. https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg#/media/File:Konigsberg_bridges.png https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg#/media/File:K%C3%B6nigsberg_graph.svg The bridges of Königsberg and friends are very popular. https://www.youtube.com/watch?v=fhJO2WHRRuY https://www.youtube.com/watch?v=nZwSo4vfw6c https://www.youtube.com/watch?v=W18FDEA1jRQ https://www.youtube.com/watch?v=2iovbcPwAro https://www.youtube.com/watch?v=IIcwc09PmXU

Download

1 formats

Video Formats

360pmp424.0 MB

Right-click 'Download' and select 'Save Link As' if the file opens in a new tab.

What is...the difference between Eulerian and Hamiltonian graphs? | NatokHD