MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs containing all $n$ vertices does $G$ have? (In other words, how many connected factors $G$ has?) Is there an algorithm that generates all such cases?

For example:

1) the Graph 0--0--0--0--0 has only one such factor.

2) a complete graph has loads of such factors (see Are there more connected or disconnected graphs on n vertices? )

The case I am working on lays somewhere between the above two examples. In my situation, $n$ is large (say 3000) but the graph is sparse in the sense that each vertex has degree at most equal to 20 or 30. Furthermore, I have a notion of distance between points - far away points cannot share an edge. The situation is similar to connecting the cities of a country with roads - there are loads of cities, but each city will have few roads emanating from it, and cities that are far away will not share a direct road. All cities should connected to the transportation grid. How many such grids are there? In other words, I am trying to count the number of $(1,20)$-Factors. I need to know this number to check if the brute force computation I am considering is not feasible.

share|cite|improve this question
Pick a connected spanning tree of your labeled graph. It has N edges, and your graph has about 10N edges. This alone suggests at least 500^N connected subgraphs which contain this tree. I would not attempt brute force for N greater than 22. – The Masked Avenger Jan 31 '14 at 23:38
Thanks a lot Avenger. – user3487 Jan 31 '14 at 23:54
Would you know, by any chance, how many spanning trees are there? – user3487 Jan 31 '14 at 23:57
1's_theorem counts spanning trees. – Benjamin Young Feb 1 '14 at 2:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.