Return to Answer

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
2. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
3. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is weakly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is Dedekind finite.
2. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
3. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
4. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is weakly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
2. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
3. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is strongly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
2. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
3. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is weakly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, I claim that it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false, if one should use Dedekind's notion of finiteness in place of the usual notion. Namely, a set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
2. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
3. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is strongly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$

Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to be finite.

Namely, if we use Dedekind's notion of finiteness, then it is relatively consistent with ZF that the infinitary Seymour graph conjecture is false. A set is Dedekind finite, when it is not bijective with any proper subset.

Theorem. It is relatively consistent with the Zermelo Fraenkel ZF axioms of set theory without the axiom of choice that there is a simple directed graph $\Gamma$ such that

1. The graph $\Gamma$ is weakly connected, and indeed, for any two nodes $x,y$ there is either an edge $x\to y$ or $y\to x$. So the underlying graph is complete.
2. Every node $v$ has a Dedekind finite neighbor set $N^+(v)$. Furthermore, the cardinalities of $N^+(v)$ are distinct for distinct vertices $v$.
3. Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$. Indeed, $N^{++}(v)=\varnothing$ for every node $v$.

Proof. It is well known to be relatively consistent with ZF that there is a set of real numbers $A\subseteq\mathbb{R}$ that is infinite, but Dedekind finite. We may assume that $A$ has no least element since $A$ can have at most a finite discrete order at the bottom, which upon deleting will produce an infinite Dedekind finite set with no least element.

Consider the directed graph $\Gamma$ consisting of the $>$ relation on $A$. That is, every element of $A$ points at the other elements strictly below it. Since the entirety of $A$ is Dedekind finite and $A$ has no least element, it follows that $N^+(v)$ is infinite but Dedekind finite for every vertex $v$.

And since every node points at all the lower nodes, the graph relation is transitive, it follows that $N^{++}(v)=\varnothing$, as it is defined in the OP. Thus, $N^{++}(v)$ is strictly smaller in cardinality than $N^+(v)$. So this graph has the desired properties.

Note that the neighbor sets $N^+(v)$ strictly descend in cardinality as $v$ descends in $A$, since if $v<w$ then the predecessors of $v$ in $A$ cannot be placed into bijection with the predecessors of $w$ in $A$, since this would lead to a nontrivial bijection of $A$ with a proper subset of itself, which is impossible for a Dedekind finite set. $\Box$

The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree. This answers the version of the question mentioned by Louis D in the comments of the OP.

Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that

1. The digraph is weakly connected, with the underlying graph complete.
2. Every $N^+(v)$ is infinite.
3. Every $N^{++}(v)=\varnothing$ is empty.

Proof. The graph consisting of the $>$ relation, meaning that every node points at the nodes strictly below it, has every $N^+(v)$ as the set of smaller nodes. This is strongly connected, since any two distinct nodes are related one way or the other. Since there is no minimal element, these sets are all infinite. But $N^{++}(v)=\varnothing$ is empty, because the relation is transitive. $\Box$