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