Pósa's Theorem

Let $G$ be a Simple Graph with $n$ Vertices.

1. If, for every $k$ in $1\leq k<(n-1)/2$, the number of Vertices of Valency not exceeding $k$ is less than $k$, and

2. If, for $n$ Odd, the number of Vertices with Valency not exceeding $(n-1)/2$ is less than or equal to $(n-1)/2$,

then $G$ contains a Hamiltonian Circuit.

See also Hamiltonian Circuit