# How this tree has 6 subtress?

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.

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?

Thanks.

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.

• 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). – Arthur Nov 4 '18 at 7:52
• Are you allowed to consider the empty tree as a subtree? – John Douma Nov 4 '18 at 7:58
• empty tree not allowed. updated the problem description with the definition of subtree. – 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.

• 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? – user3243499 Nov 4 '18 at 8:24
• @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). – Parcly Taxel Nov 4 '18 at 8:26
• then what if I have a tree with a single node. You mean there is no subtrees in a tree of 1 node? – user3243499 Nov 4 '18 at 8:27
• @user3243499 In that case, there is exactly one subtree in a tree of one node: the whole tree itself. – Parcly Taxel Nov 4 '18 at 8:28
• 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. – user3243499 Nov 4 '18 at 8:29