# Why is counting the number of hamiltonian subgraphs $\sharp P$ hard?

I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032

1) "A further problem that can be shown to be #P-hard is that of counting the number of Hamiltonian subgraphs of an arbitrary directed graph." (I think he means subgraphs as sets of edges, not induced by nodes.)

2) "Given a complete graph on n nodes and arbitrary probabilities assigned to each edge, the probability that the graph has a Hamiltonian circuit (or some other NP-complete substructure) is easily seen to be #P-complete."

Given $$1)$$, it's easy to see that $$2)$$ problem is $$\sharp P$$ hard$$^*$$, but it's unclear to me why this problem is in $$\sharp P$$. Valiant mentions that $$1)$$ is likely not in $$\sharp P$$, so maybe this is a typo. $$2)$$ appears to perhaps even strictly harder than $$1)$$.

Can anyone give me a hint on how to think about $$1)$$?

(*In the following way: For any given graph $$G$$, embed $$G$$ into a complete graph. On that complete graph, set the probabilities for edges not in the embedding to zero, and for edges in the embedding to $$1/2$$. Then each subgraph of $$G$$ has probability $$(1/2)^{E(G)}$$ of appearing, so the probability that the random subgraph has a HC can be used to easily determine the number of subgraphs with Hamiltonian cycles. This shows that (given 1) ) it is $$\sharp P$$ hard to compute those probabilities.)

In this paper they also show that a version of 1) is Span-P complete (page 375). The only difference is that a number $$k$$ is also part of the input and they want only the Hamiltonian subgraphs of size $$k$$ (I'm assuming the "positive integer $$c$$" was a typo). Also at the end of Section 6 ("A variation of the above...") they specifically mention your problem (so without the restriction of size $$k$$) and they that they do not know if it is Span-P hard.