Hamiltonian path

Remarks

Since a path visits each vertex at most once, a Hamiltonian path of a graph with $n$ vertices visits each vertex exactly once and has length $n - 1$. Deleting one edge from a Hamiltonian cycle gives a Hamiltonian path, so every Hamiltonian graph has one. The converse fails: the Petersen graph has a Hamiltonian path but no Hamiltonian cycle. Example: in the cycle graph $C_4$ with vertices $1, 2, 3, 4$ in cyclic order, the path $(1, 2, 3, 4)$ contains all four vertices, so it is a Hamiltonian path. Non-example: the star $K_{1,3}$ with centre $c$ and leaves $a, b, d$ has no Hamiltonian path. Each edge contains $c$, so a path alternates between $c$ and leaves, and since it visits $c$ at most once, it contains at most two leaves. A graph with a Hamiltonian path is connected.