It is consistent with ZF, I claim, 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
- The graph $\Gamma$ is strongly 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.
- Every node $v$ has a Dedekind finite neighbor set $N^+(v)$.
- Every $N^{++}(v)$ has strictly smaller cardinality than $N^+(v)$.
- Indeed, $N^{++}(v)=\varnothing$ will be empty 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. $\Box$
The same idea works as a theorem, and not just a relative consistency result, if one allows nodes to have infinite degree.
Theorem. The digraph consisting of the $>$ relation on an endless linear order has the properties that
- The digraph is strongly connected, with the underlying graph complete.
- Every $N^+(v)$ is infinite.
- 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$