# Category of Trees as sub-category of Category of Graphs

A tree (like a binary search tree) is a direct graph with some limitations (no cycles, connected). How can I express the category of trees as "sub-category" of a graphs? There is a way? I'm not sure the term "sub-category" is correct.

-
What do you mean by "express"? You can just say that $\mathcal{T}$ is a category with objects being trees and morphisms being homomorphisms of trees (graphs -- it's a full subcategory of the category $\mathcal{G}$ of graphs). –  Damian Sobota Feb 12 '12 at 13:27
"define" is better than "express" –  tyranitar Feb 12 '12 at 13:41
So I wrote you an answer. What do you need more? –  Damian Sobota Feb 12 '12 at 13:55

I think the term you're looking for is "full subcategory". If you have a category $C$, and a set $d$ of objects in $C$, then the full subcategory of $C$ defined by $d$ is the category $D$ whose objects are the elements of $d$, and whose morphisms are all the morphisms of $C$ whose domain and codomain are in $d$. Thus, you can simply say:

"Define the category Tree as the full subcategory of Gph whose objects are trees."

-
That's exactly what I said in a comment. –  Damian Sobota Feb 12 '12 at 21:14
@DamianSobota: you could make that a full answer rather than a comment. –  Mitch Feb 13 '12 at 2:34
Another possibile definition is 'a finite poset with a smallest element and such that for every element the down-set determined by it is linearly ordered'. It too captures the same notion of "tree" as above and yields yet another category of trees, the full subcategory of the category of posets spanned by those trees. There is also the dendroidal category $\Omega$ whose objects are trees and can be defined in at least three different ways.