How do I prove that the number of $2-$cycles on $ \{1,\dots, k \}$ is at most $k^2 k{!}$.
I know that a $2-$ cycle is a graph obtained either by joining two simple cycles by a simple path or by connecting two vertices of a simple cycle by a simple path.
But I am stuck on how to find the combinatorial formula. Any help or hint is appreciated. Thanks in Advance!