Approach to counting the number of sub-graphs of a given graph $G = (V,E)$ I have just currently started reading about Graph theory in computer science and while reading the concept of graphs I came across the concept of sub-graphs. As a sub-graph is essentially similar to a subset in set theory I became interested in the question
"How many sub-graphs exist for a given graph G = (V,E)"
While trying to count the number of sub-graphs I got a little confused as to what should be a generic approach in order to try figure out the number of sub-graphs quickly as it is highly dependent on the edge set the given graph possesses and this question confirmed my intuition : How many subgraphs of this simple graph?. But even this question doesn't answer the generic question as to what should be the general approach to figure out the number of sub-graphs for a given graph quickly. It will be great if someone could throw some light on the approach and explain it like they were explaining it to a 5 year old.
 A: I can't explain this approach to a five-year-old child. But here are my considerations, which work for any graph, but perhaps not very effectively from the  computer science point of view.

*

*Any graph of order $n$ has an empty subgraph and $n$ single-vertex subgraphs.


*More generally, there are $n\choose k$ possibilities to choose $k$ vertices from $n$.


*If a graph of order $k$ has $m$ edges, then it has $2^m$ different subgraphs of order $k$.


*Applying considerations 3 and 4 for each $k=2,\ldots,n$ we can compute the total number of subgraphs of a given graph.
Addition. For example, for the graph in this post
How many subgraphs of this simple graph? it looks like this:


*empty subgraphs  $(1)$


*subgraphs with a single vertex $(4)$


*subgraphs with two vertices - $6$ of them
2a. three have no edges $(3)$
2b. three have exactly one edge $(3\cdot2)$


*subgraphs with three vertices - $4$ of them
3a. one has no edges $(1)$
3b. three have exactly two edges $(3\cdot2^2)$


*subgraphs with four vertices $1$. It has three edges ($2^3$)
Now let's sum up all the numbers in brackets
$$
1+4+3+3\cdot2+1+3\cdot2^2+2^3=35.
$$
