title: Find all subtrees of size N in an undirected graph
body: <p>Given an undirected graph, I want to generate all subgraphs which are trees of size N, where <em>size</em> refers to the number of edges in the tree.</p>
  
  <p>I am aware that there are a lot of them (exponentially many at least for graphs with constant connectivity) - but that's fine, as I believe the number of nodes and edges makes this tractable for at least smallish values of N (say 10 or less).</p>
  
  <p>The algorithm should be memory-efficient - that is, it shouldn't need to have all graphs or some large subset of them in memory at once, since this is likely to exceed available memory even for relatively small graphs.  So something like DFS is desirable.</p>
  
  <p>Here's what I'm thinking, in pseudo-code, given the starting graph <code>graph</code> and desired length <code>N</code>:</p>
  
  <p>Pick any arbitrary node, <code>root</code> as a starting point and call <code>alltrees(graph, N, root)</code></p>
  
  <pre><code>alltrees(graph, N, root)
   given that node root has degree M, find all M-tuples with integer, non-negative values whose values sum to N (for example, for 3 children and N=2, you have (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0), I think)
   for each tuple (X1, X2, ... XM) above
     create a subgraph "current" initially empty
     for each integer Xi in X1...XM (the current tuple)
      if Xi is nonzero
       add edge i incident on root to the current tree
       add alltrees(graph with root removed, N-1, node adjacent to root along edge i)
     add the current tree to the set of all trees
   return the set of all trees
  </code></pre>
  
  <p>This finds only trees containing the chosen initial root, so now remove this node and call alltrees(graph with root removed, N, new arbitrarily chosen root), and repeat until the size of the remaining graph &lt; N (since no trees of the required size will exist).</p>
  
  <p>I forgot also that each visited node (each root for some call of alltrees) needs to be marked, and the set of children considered above should only be the adjacent unmarked children.  I guess we need to account for the case where no unmarked children exist, yet depth > 0, this means that this "branch" failed to reach the required depth, and cannot form part of the solution set (so the whole inner loop associated with that tuple can be aborted).</p>
  
  <p>So will this work?  Any major flaws?  Any simpler/known/canonical way to do this?</p>
  
  <p>One issue with the algorithm outlined above is that it doesn't satisfy the memory-efficient requirement, as the recursion will hold large sets of trees in memory.</p>