Lets define *edge-cycle* in a graph $G$ as a path where the first and the last node are adjacent.
(in contrast with the definition of *cycle* where first and last node are the same).


An *edge-tree* $T$ is a tree with the additional property that doesn't have an edge-cycle.


In a graph we can compute the number of spanning trees by using the [Matrix-Tree](http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem) theorem.



> 
> Is there any similar theorem for the computation of the number of edge-trees of a graph?
> 
> 
> 



on counting of special case of trees on a graph
I'll answer a question raised in the comments:


**Problem**: Count the number of induced trees of size $k$.


According to this [paper](http://www.renyi.hu/~p_erdos/1986-08.pdf) by Erdös, Saks and Sos, it is NP-complete to decide given a graph $G$ and an integer $k$, if $G$ contains an induced tree of size $k$. So, it's probably pretty damn hard to count them. Apparently, it remains NP-complete even for bipartite graphs. 


Actually, the argument is pretty simple so I'll include it here. Given a graph $H$ and an integer $k$, it is well-known that the problem of deciding if $H$ has an independent set of size $k$ is NP-complete. Suppose that $H$ has $n$ vertices. Let $G$ be the graph obtained from $H$ by first adding a disjoint copy of $P\_n$ (a path on $n$ vertices), and then connecting one end of $P\_n$ to all the vertices in $H$. Clearly, $H$ has an independent set of size $k$ if and only if $G$ contains an induced tree of size $n+k$. 


