enter image description here

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?

  • $\begingroup$ There are 5 edges in the $\{A,C,E,G\}$ component $\endgroup$ – TokenToucan Dec 22 '15 at 7:39
  • $\begingroup$ sorry , I missed that one edge so then it will be 32+2=34 subgraphs possible , right ? $\endgroup$ – radhika Dec 22 '15 at 7:44
  • $\begingroup$ It doesn't matter that the components are disconnected. $\endgroup$ – TokenToucan Dec 22 '15 at 16:06
  • $\begingroup$ So then what should be the approach ? $\endgroup$ – radhika Dec 22 '15 at 16:26
  • $\begingroup$ Exactly what you were doing before, $2^6=64$ $\endgroup$ – TokenToucan Dec 22 '15 at 16:37

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

enter image description here

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

| cite | improve this answer | |
  • $\begingroup$ 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 ? $\endgroup$ – radhika Dec 26 '15 at 4:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.