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?
2026-05-17 09:49:49.1779011389
On
On
Is it possible to make an infinite directed acyclic graph with all vertices having a indegree of at least one
820 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
1
On
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$
0
On
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...
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.