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

820 Views Asked by At

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?

3

There are 3 best solutions below

3
On 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.

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