# Is it possible to make an infinite directed acyclic graph with all vertices having a indegree of at least one

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?

• What about $\mathbb{Z}$ as a vertex set of a directed graph, with $(m,m+1)$ an edge for every $m\in \mathbb{N}$? Is that not an example? Commented Feb 2, 2020 at 15:20
• I wonder if you're saying "finite" when you mean "infinite" and vice versa? Because it's actually not possible to create a finite DAG where every vertex's indegree is at least one. Commented Feb 4, 2020 at 7:50

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.

• Don't you mean “for each integer $i \in \mathbb{Z}$” instead of “for each natural number $i \in \mathbb{N}$”? Commented Oct 19, 2021 at 19:29
• Arrows go down, so vertex $0$ doesn't have an arrow out, but everyone has an arrow in.
– Jim
Commented Oct 19, 2021 at 23:43
• Ah yes, of course. I should have read your answer more carefully. Thanks! Commented Oct 21, 2021 at 12:31

Let $$G=(V,E)$$ where $$V=\mathbb Z$$, and $$E=\{(a,b)\mid a+1 = b\}$$.

This graph is obviously infinite, with in and out degree equal to $$1$$

• You can extend this to $V=\mathbb R$ for an uncountable example Commented Feb 3, 2020 at 1:58

It is possible to make a directed acyclic graph with all vertices having a countably infinite indegree: start with a single vertex at Stage $$0$$; and at Stage $$n+1$$, for each vertex created in Stage $$n$$ you simply add countably infinite vertices that point to it.

This probably works for higher infinities as well, but there might be set-theoretic subtleties involved, and it's getting late here...