3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Feb 2, 2020 at 15:20
  • $\begingroup$ 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. $\endgroup$
    – ruakh
    Commented Feb 4, 2020 at 7:50

3 Answers 3

6
$\begingroup$

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.

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

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$

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .