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

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?

share|cite|improve this question
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 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
up vote 3 down vote accepted

I'll answer a question raised in the comments:

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

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


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

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