Approach to counting the number of sub-graphs of a given graph $G = (V,E)$

Solution 1:

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.

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

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

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

4. 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:

0. empty subgraphs $(1)$

1. subgraphs with a single vertex $(4)$

2. subgraphs with two vertices - $6$ of them

   2a. three have no edges $(3)$

   2b. three have exactly one edge $(3\cdot2)$

3. subgraphs with three vertices - $4$ of them

   3a. one has no edges $(1)$

   3b. three have exactly two edges $(3\cdot2^2)$

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