I have got a graph theory question from a friend as follows:

It is a tree as shown below rooted at "a". And asks me to find the number of subtrees it has.

enter image description here

I have found 5 subtrees as marked in red cirles. He says, it is 6. Am I missing any possible subtree, which by definition is a subtree?


Updated: Definition of subtree -

Subtree is a non-empty subgraph satisfying the following condition: For any vertex x, if x belongs to subtree P, then the parent of x also belongs to P. Note that each subtree contains the root.

  • $\begingroup$ What is your definition of a "subtree"? Because I see many more subgraphs which are trees (a-d-e and a-b-c, for instance). $\endgroup$ – Arthur Nov 4 '18 at 7:52
  • $\begingroup$ Are you allowed to consider the empty tree as a subtree? $\endgroup$ – John Douma Nov 4 '18 at 7:58
  • $\begingroup$ empty tree not allowed. updated the problem description with the definition of subtree. $\endgroup$ – user3243499 Nov 4 '18 at 8:02

By your definition, there are actually nine subtrees: $$abcde,abde,ade,abcd,abd,ad,abc,ab,a$$ This can be understood by considering at which points the subtree branches stop at, for each branch of the original tree. For the left branch we have a choice in $A=\{a,b,c\}$ and for the right one we have a choice of $B=\{a,d,e\}$. The nine trees are obtained by starting from a choice of vertices in $A×B$ and extending this choice to a complete subtree.

  • $\begingroup$ This is so confusing. How is abe a subtree? If it is then why not adc? and how is "a" a subtree? why are "c" and "e" not subtrees? $\endgroup$ – user3243499 Nov 4 '18 at 8:24
  • $\begingroup$ @user3243499 whoops, I typoed, should be ade and not abe. c and e (by themselves) are not subtrees because they don't contain their parents (b in the case of c, d for e). $\endgroup$ – Parcly Taxel Nov 4 '18 at 8:26
  • $\begingroup$ then what if I have a tree with a single node. You mean there is no subtrees in a tree of 1 node? $\endgroup$ – user3243499 Nov 4 '18 at 8:27
  • $\begingroup$ @user3243499 In that case, there is exactly one subtree in a tree of one node: the whole tree itself. $\endgroup$ – Parcly Taxel Nov 4 '18 at 8:28
  • $\begingroup$ got it. Just one more clarification. What if it is a tree with 2 nodes, say "a-b"? How many subtrees would be there? "a" is the root. $\endgroup$ – user3243499 Nov 4 '18 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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