I got stuck on the connection between Hamiltonian circles and $k$-factors, can someone show me how one can find such a connection to get along with the problem?
Wikipedia's definitions: In graph theory, a factor of a graph $G$ is a spanning subgraph, i.e., a subgraph that has the same vertex set as $G$. A $k$-factor of a graph is a spanning $k$-regular subgraph, and a $k$-factorization partitions the edges of the graph into disjoint $k$-factors. If such a factorization exists we call G, a $k$-factorable graph.
Dirac's theorem: A $\nu$-vertex graph in which $\nu\ge 3$ each vertex has degree at least $\frac\nu2$ is Hamiltonian.
Use dirac's theorem on the graph to extract a hamiltonian cycle. Number the edges of the cycle and remove the even ones.
We now have a graph $G'$ which has minimmum degree at least $\nu/2$. So we can extract a hamiltonian cycle from $G'$.
The $3$-factor we need consists of the new hamiltonian cycle, plus the edges we had originally deleted from $G$.