Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only finitely many edges going out of it. The first neighborhood $N^+(x)$ is the set of all $y\in G$ such that there is an edge $x\to y$. The second neighborhood $N^{++}(x)$ is everything reachable in exactly two steps from $x$: all $z\not\in N^+(x)\cup \{x\}$ such that there is some $y\in G$ with $x\to y\to z$.

A well-known conjecture of Seymour states that if $G$ is a **finite** nonempty directed graph then there exists some $x\in G$ with $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$. This is still open (but see e.g. Seymour's second neighborhood conjecture for some partial results).

What is the status of Seymour's second neighborhood conjecture for infinite (but still locally finite) connected graphs?

That is,

If $G$ is an infinite, locally finite, graph, must there exist some $x\in G$ such that $\lvert N^+(x)\rvert \leq \lvert N^{++}(x)\rvert$?

I ask mainly because it seems a natural generalisation, but to my surprise I can't find any discussion of it in the literature. Perhaps this is because it's 'trivial' for some reason that I can't see. Possibilities:

- It's easily false, there is a simple construction of an infinite $G$.
- It's easily true, there is some simple argument in the infinite case I can't see.
- It's equivalent to the regular, finite graph, conjecture via some simple(ish) argument.
- It's a genuinely different, hard, conjecture.

I've added the model-theory tag because I've mentioned this to a logician who suggested that possibility (3) might hold via some general model-theoretic argument (reducing the 'infinite model' of $G$ to some finite model somehow), but I don't know any details, and perhaps this just doesn't work.

(The restriction to locally finite is mainly so that the sizes of these neighborhoods are finite numbers, which I prefer thinking about. I don't know, but would be interested in, an answer even allowing the sizes of these neighborhoods to have infinite cardinalities.)

Any insights, answers, or pointers to somewhere in the literature this has been discussed and I've missed, would be appreciated.

EDIT: As Tony Huynh has pointed out in the comments, the infinite version implies the finite version (even if we ask for the infinite graph to be weakly connected). So (2) is unlikely, and the hard part of proving equivalence is showing that the finite case implies the infinite case.

9more comments