1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ One can prove that a finite digraph is an arborescence if and only if its a polytree with one source vertex. Where an abhorrence is a connected acyclic digraph all of whose vertices (other then possibly a source vertex) have an in-degree of one. With that said I was hoping to try and fiind some criteria for abhorrences with no source vertex involving polytrees. Do you think its possible to add more preliminary restrictions to my polytree to ensure that every vertex has in-deree of one? Where again its clear none of these polytrees are going to be finite. $\endgroup$ – Ethan Aug 4 '18 at 22:06
  • $\begingroup$ @Ethan: You can take an arbitrary infinite rooted tree without leaves and point all edges towards the root. Then you can have as large indegrees as you want to. $\endgroup$ – Henning Makholm Aug 4 '18 at 22:12
  • $\begingroup$ Ahh damnet. I think the finite result hinges on the fact that a directed acyclic graph is rooted iff it has one source vertex. Thanks anyway though. $\endgroup$ – Ethan Aug 4 '18 at 22: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.