If an orientation of a tree graph has no source vertices, must the in-degree of each vertex in said orientation be equal to one?

92 Views Asked by At

Given any polytree $T$ (any orientation of a tree graph) such that $\forall v\in V(T)(\text{indeg}(v)\neq 0)$ does this imply that $\forall v\in V(T)(\text{indeg}(v)=1)$? I'm pretty sure its true, but I'm having a rather hard time constructing a proof. Also it's clear that any such digraph $T$ is non-finite, since any directed acyclic graph with no source vertices must necessarily contain an in-ray and thus can't be finite.

1

There are 1 best solutions below

3
On BEST ANSWER

Counterexample: $$ \cdots \to \bullet \to \bullet \to \bullet \leftarrow \bullet \leftarrow \bullet \leftarrow \cdots $$

(A doubly-infinite path with all edges pointing towards a designated center).