DIscrete maths:- Graph theory

Question

Number of subgraphs possible with K4?  

Given answer is 106 .I think 112 is correct?

Comments

You can choose the vertices as well

---

@sukanya @nitish may you post the detailed solution?

---

Formula is = $\sum_{r=1}^{n}\binom{n}{r} 2^{r(r-1)/2}$

Answer 1

Since, there are 4 vertices and 6 edges, so the following cases are possible:

Case1: 1 vertex graph

 Choose 1 out of 4 vertices= $4C1$ = $4$

 Total number of 1 vertex graph =$4$

Case2: 2 vertices graph:

           Choose 2 out of 4 vertices=$4C2$=6

       Either you connect the vertices with a edge or you don't in 2 ways

       Total number of 2 vertices graph= $6*2$=12

Case3: 3 vertices graph:

     Choose 3 out of 4 vertices= $4C3$=4

    There may be atmost 3 edges in such a graph and so the vertices can be connected in= $2^3=8$ ways

    Total number of 3 vertices graph= $4*8=32$ 

Case 4: 4 vertices graph

Choose all the vertices=1 way

There may be atmost 6 edges and so the vertices can be connected in=$2^6=64$ ways

Total number of 4 vertices graph=$64*1$=64

$\therefore$ Total number of subgraphs= $4+12+32+64=112$