# 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

To make sure we're on the same page, this should be the graph:

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$?)

• Can you please tell the cases where we will have vertices less than 6 , say I have only A and E and they are disconnected so how to deal with those cases ? – radhika Dec 26 '15 at 4:01