New to graph theory and I'm surprised I cannot find any solid clarification on this: For two nodes and one undirected connecting edge, can this be considered a tree graph where both nodes are leaves-- or is the minimum number of nodes on a tree graph three? What about if the connecting edge is directed?


This is a tree. A tree is a connected, acyclic graph. A single edge certainly satisfies this definition.

| cite | improve this answer | |
  • $\begingroup$ Thanks for that clarification. Regarding the undirected edge connecting them, wouldn't that entail both nodes have a child (each other)? I'm trying to understand if that gives us one or two leaves, since leaves cannot have child nodes. $\endgroup$ – Ryan Nov 23 '17 at 0:08
  • 1
    $\begingroup$ @Ryan: If your'e speaking about parent and child nodes, then the concept you want is (in graph theory vocabulary) rooted trees rather than just trees. Your two-node graph becomes a rooted tree if you declare one of the nodes to be the root. (And the root of a rooted tree would not usually be considered a leaf, except in the trivial tree with only one node and no edges). $\endgroup$ – hmakholm left over Monica Nov 23 '17 at 0:10
  • $\begingroup$ @HenningMakholm Oh I see, yes I was definitely mixing up the graph classifications. My sample is not rooted, so then I suppose that would entail two leaves. (And thanks for the clarification!) $\endgroup$ – Ryan Nov 23 '17 at 0:14

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.