# on counting of special case of trees on a graph

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 theorem.

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

-
What is the difference between "no edge-cycle" and "no cycle"? – darij grinberg Sep 3 '10 at 13:55
Or does "adjacent" mean "adjacent in the ambient graph"? – darij grinberg Sep 3 '10 at 13:55
Well, technically katsarola wanted to count edge-trees, not necessarily spanning edge trees, even though the Matrix-Tree theorem counts spanning trees. If spanning edge-trees are wanted, then there is 1 if the graph is a tree, and none otherwise. If it's edge-trees that are wanted, it looks like we just want to count induced subgraphs that are trees. – Tony Huynh Sep 3 '10 at 14:51
So an edge-tree is what is more commonly called an induced tree, right? – David Eppstein Sep 3 '10 at 15:57
The point of this comment is to explain why your definition is the same as "induced trees". Let S be a set of vertices of G. Let H by the subgraph induced by S en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs. I claim that there is an edge-tree with vertex set S if and only if H is a tree. Proof: Clearly, if H is a tree, it is an edge tree. Now, let T be a tree with vertex set S. Suppose that (u,v) is an edge of H not in T. Trees are connected, so there is a path through T from u to v. Adding the edge (u,v) to this path shows that T is not an edge-tree. – David Speyer Sep 3 '10 at 16:36

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

According to this paper 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$.

-

If I'm reading your definitions right, I believe the answer is that there are zero edge-trees of G if G has any cycle. And one if G is a tree itself (T=G)

Proof: If G has a cycle C, then for any spanning tree T of G there exist an edge E(u,v) of C that is not in T. Since T is a spanning tree, there is a path from u to v in T, and u and v are adjacent in G, thus the path from u to v is an edge-cycle, therefore there is always an edge-cycle in T. Therefore there are zero edge-trees of G.

-
I don't think the edge trees are required to be spanning trees. – Gjergji Zaimi Sep 3 '10 at 14:56
I thought this too initially (but it's not right). Take the 3-cycle on vertices {a,b,c}, add a vertex e and an edge between a and e. Then eabc and eacb are both spanning trees whose endpoints are not adjacent. – Douglas S. Stones Sep 3 '10 at 15:03
But eabc is not a spanning edge-tree, since it contains abc which is an edge cycle. – Tony Huynh Sep 3 '10 at 15:07