Made Easy: Counting number of subgraphs of the given graph. How should I approach this question?

Question

Comments

how 121 is correct answer?
consider the case in which sub-graph has only 2 vertices. so there are 10 ways to select 2 vertices.i’m not using set notation but you can understand.
these 10 ways to select 2 vertices are AB,AC,AD,AE,BC,BD,BE,CD,CE,DE.
out of these 10 pairs of vertices each AB,BC,CD,DE,AE will give me 2 sub-graphs. and remaining pair of vertices will give me total 5 sub-graphs.
so total i got 15 sub-graphs when i select only 2 vertices.how they are getting 20 sub-graphs with only 2 vertices?

---

For 2 vertices,

 no. of possible subgraphs $=\binom{5}{2} \times 2^1 = 20$

Here $2^1$ denotes no. of ways to select edges. For 2 vertices, we can have 1 edge. So we can choose to either add the edge or not.

---

what is wrong in my logic?

---

@rexritz 
Building on your logic, for 5 vertices, 

no. of possible subgraphs = $\binom{5}{5}\times 2^5$ = 32

As for 5 vertices, we can have 5 edges, right? Why are they not considering the cycle graph in any case? Please help

---

Yes @tishhaagrawal you are right. For 5 vertices answer should be 32.

---

@parth023 I think you are right, we will get only 15 subgraphs if we choose 2 vertices from the given graph.

But counting all the subgraphs present in the given graph using this approach will be very tedious, also we might miss some of the subgraphs in this approach!

The solution provided by Made Easy is surely wrong, but can you explain a systematic way to get to the answer, please

---

@tishhaagrawal i’m getting 123 as answer, plus the best “systematic way” i can think is just go by number of vertices.may be there is some formula for counting number of sub-graphs in some special graphs like cycle or complete graph but i don’t know about that.