# How to find number of sub-graphs with given $6$ vertices? In this quest, I got two disconnected components wherein one connected component had vertices $\{A,E,C,G\}$ and another disconnected component had vertices $\{S,T\}$, so now to calculate total number of subgraphs , each edge has two choices either it can be a part of sub-graph or not a part of sub-graph. Now since there are $4$ edges in one-subgraph so for them total number of choices will be $16$ and for second component $2$ choices, so according to me total no of sub-graphs should be $18$, what is the mistake in this approach?

• There are 5 edges in the $\{A,C,E,G\}$ component – TokenToucan Dec 22 '15 at 7:39
• sorry , I missed that one edge so then it will be 32+2=34 subgraphs possible , right ? – radhika Dec 22 '15 at 7:44
• It doesn't matter that the components are disconnected. – TokenToucan Dec 22 '15 at 16:06
• So then what should be the approach ? – radhika Dec 22 '15 at 16:26
• Exactly what you were doing before, $2^6=64$ – TokenToucan Dec 22 '15 at 16:37 There are $6$ edges, and hence $2^6$ labelled subgraphs on $6$ vertices (there are $2^6$ subsets of the edge set).
It should be 32*2=64 rather than 32+2=34, as for each $4$-vertex subgraph of the big component and $2$-vertex subgraph of the small component, we can combine them to give a unique $6$-vertex subgraph of the whole graph.
There seems to be no sensible way to derive an answer of 7 from this question. (Does $G=G_L$?)