Counting specific subgraphs For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions:


H.V = G.V (The subgraph will containt all the original graph nodes)
H is connected


(Note: I don't care if two subgraphs are isomorphic)

The graphs which I will be working with will have |G.V| &lt;= 15
Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.

The number of connected spanning subgraphs of a graph $G$ equals $T_G(1,2)$, where $T_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence this paper of Björklund et al., which shows how to compute said polynomial in vertex-exponential time (i.e., $\exp O(n)$), gives us hope, since in your case $n$ is pretty small ($n \leq 15$).