Editing Hamiltonian path (section)

==Properties==
[[Image:Herschel Hamiltonian path.svg|thumb|The [[Herschel graph]] is the smallest possible [[polyhedral graph]] that does not have a Hamiltonian cycle. A possible Hamiltonian path is shown.]]
Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to a Hamiltonian cycle only if its endpoints are adjacent.

All Hamiltonian graphs are [[Biconnected graph|biconnected]], but a biconnected graph need not be Hamiltonian (see, for example, the [[Petersen graph]]).<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=Biconnected Graph|author=Eric Weinstein|publisher=Wolfram MathWorld}}</ref>

An [[Eulerian graph]] {{mvar|G}} (a [[connected graph]] in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of {{mvar|G}} exactly once. This tour corresponds to a Hamiltonian cycle in the [[line graph]] {{math|''L''(''G'')}}, so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph {{math|''L''(''G'')}} of every Hamiltonian graph {{mvar|G}} is itself Hamiltonian, regardless of whether the graph {{mvar|G}} is Eulerian.<ref>{{citation|title=A Textbook of Graph Theory| first1=R.|last1=Balakrishnan| first2=K.|last2=Ranganathan| publisher=Springer| year=2012| isbn=9781461445296| contribution=Corollary 6.5.5|page=134|url=https://books.google.com/books?id=mpgu6wgnZgYC&pg=PA134}}.</ref>

A [[Tournament (graph theory)|tournament]] (with more than two vertices) is Hamiltonian if and only if it is [[Strongly connected component|strongly connected]].

The number of different Hamiltonian cycles in a complete undirected graph on {{mvar|n}} vertices is {{math|{{sfrac|(''n'' − 1)!|2}}}} and in a complete directed graph on {{mvar|n}} vertices is {{math|(''n'' − 1)!}}.  These counts assume that cycles that are the same apart from their starting point are not counted separately.