Number of complex components with l=1 in G(n,p)

56 Views Asked by At

I need to prove that the number of specific components with complexity one, that is, two cycles connected by a path or an edge and one cycle with an inner path, on the set of vertices $\{1\ldots k\}$ is at most $k^2k!$. I have been reading in some books that this is a very easy proof but i cant get into it. I know that the number of cycles with $k$ vertices on a graphs are $\sum_{i=3}^{k}\binom{k}{i}\cfrac{i!}{2i}$ but actually i don't know how to get to $k^2k!$. Any hint will be appreciated!