# 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| <= 15

• Are you interested in the number of nonisomorphic graphs or the total of all (connected) subgraphs? In either case, you could help us to help you by describing what you've tried so far. – Rick Decker Jun 7 '16 at 13:57
• What do you mean by "H.V" and "G.V"? – David Richerby Jun 7 '16 at 15:21
• By H.V do you mean the vertices of H? – Michael Klein Jun 7 '16 at 17:42
• The subgraph will containt all the original graph nodes – Jaldemad Sama Jun 7 '16 at 18:34
• Still it would be nice to answer to comments by editing the question. – Evil Jun 7 '16 at 18:38

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$).