Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter). Then how many connected induced subgraphs of size $l$ does $G$ have?

The simple case when $l=2$, The number of subgraphs is number of edges which is $O(nk)$. How can we generalize this one.

  • 3
    $\begingroup$ It is hard to tell whether you are asking for the max possible number (over all graphs on n vertices and kn edges) or whether you mean an expected number, or something else. If you do mean expected or average number, then you need to mention the distribution of graphs in consideration. $\endgroup$
    – JimN
    Commented Mar 24, 2014 at 7:33
  • $\begingroup$ I am looking for max possible number of subgraphs. Actually number of edges I have is $kn-\frac{k(k+1)}{2}=O(nk)$. $\endgroup$
    – Kumar
    Commented Mar 24, 2014 at 8:21
  • $\begingroup$ I think it would help if you state the entity that you want to count more formally inside the question. And are we counting up to isomorphism or not? $\endgroup$
    – Kaveh
    Commented Mar 24, 2014 at 9:01

2 Answers 2


Consider a star graph, if we take a center of star union with $l-1$ arbitrary vertices then the corresponding subgraph is induced connected subgraph. So the maximum number is about $n-1\choose l-1$. We can extend this class of graphs by connecting arbitrary vertices together to have more edges. It's also possible to achieve closer to $n \choose l$ if $l$ is much smaller than $k$, or $k$ is big enough.


This does not completely answer your question. I don't believe any upper bounds are known with respect to the average degree of a graph, but here is a result about graphs where the maximum degree is bounded.

Björklund et al. (2012) showed that the number of connected vertex subsets of a graph with $n$ vertices and maximum degree $d$ is at most $(2^{d+1}-1)^{n/(d+1)}+n$.

For maximum degrees 3,4, and 5, this gives the upper bounds $O(1.9680^n)$, $O(1.9874^n)$, and $O(1.9948^n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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