Is it possible to make an infinite directed acyclic graph with all vertices having a indegree of at least one. Since the graph is infinite and all vertices have a indgree of at least one, that would create cycles. Would that make a directed acyclic graph impossible to be infinite, and would always have to be finite to work?
Is it possible to make an infinite directed acyclic graph with all vertices having a indegree of at least one
discrete mathematicsgraph theory
Best Answer
Consider the graph that has one vertex $v_i$ for each natural number $i \in \mathbb N$ and an edge $v_i \to v_j$ if and only if $i = j + 1$.
It is false that being infinite with all vertexes having in degree at least one implies the existence of a cycle.