3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • $\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, 2017 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$ Nov 23, 2017 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, 2017 at 0:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .