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

combinatoricsdiscrete mathematicselementary-set-theorygraph theory

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.

Best Answer

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:

  1. empty subgraphs $(1)$

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

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

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

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

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

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

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

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

Related Question