Infinite graphs with finitely discriminable vertices Consider asymmetric unlabelled digraphs $G$ (asymmetric means |Aut($G$)| = 1).
Trivially, (i) each node $v$ can be uniquely labelled (with the pointed graph $G_v$, i.e. $G$ with distinguished node $v$), and (ii) whether there's an edge between $v$ and $w$ can be read off their labels $G_v$ and $G_w$.
Things get interesting when in the case of an (countably) infinite graph $G$ a finite induced subgraph of $G_v$ for all $v$ does suffice for (i) and (ii). Let's call such a graph and its nodes finitely discriminable.
There are two obvious examples of infinite finitely discriminable graphs:

*

*the natural number graph with edges from $n$ to $n+1$ in which each node $v$ can be labelled by the induced subgraph consisting of $v$ and its predecessors


*the graph of hereditarily finite sets with edges from $x$ to $y$ iff $x \in y$ in which each node $v$ can be labelled by its transitive closure graph TC({v})
What these two graphs do share are the Mostowski collapse conditions, i.e. their relation is set-like, well-founded and extensional.
Questions:


*

*Are the Mostowski conditions necessary and/or
sufficient for an infinite graph to be finitely
discriminable?


*If they are not necessary: what is an example of an infinite finitely
discriminable graph for which one of
them does not hold? Is the rest of them necessary, then?


*Especially: Are there undirected (i.e. not well-founded) finitely discriminable graphs?


*If the Mostowski conditions are not sufficient: can they be augmented to become sufficient, or
is there another completely different
set of sufficient conditions?

 A: (Please se the edit history for my previous answer.)
I believe the interesting question here is whether we can
assign to each node in a countable directed graph $G$ a
finite induced pointed subgraph (up to isomorphism), such that we can reconstruct $G$
knowing only those labels. Indeed, a stronger version of
this would require that we can reconstruct $G$ in a local,
continuous and computable manner, meaning that the question
of whether two nodes are connected depends only on the
(isomorphism classes of the) labels on those nodes, and not on any other
information, including $G$, and that this is computable from those labels. (In particular, for this strong version of the question, it doesn't make sense to consider a separate algorithm for each $G$, since the reconstruction procedure should be the same for every $G$.)
The idea is that we build a copy of the original graph from
these pieces by fitting them together like a puzzle.
Theorem. Every countable graph is finitely discriminable, in the sense that it has such a labeling
with finite induced subgraphs, for which there is a uniform
computable procedure to reconstruct an isomorphic copy of the graph in a local,
continuous computable manner.
Proof. Suppose $G$ is any countably infinite directed graph. Let
$\Gamma$ be a fixed computable directed graph that is
universal for all countable directed graphs. (Thus,
$\Gamma$ is something like a directed version of the random
graph.) Thus, there is an embedding $\pi:G\to\Gamma$ to an
induced subgraph of the countable random graph $\Gamma$.
Fix a computable copy of $\Gamma$, using positive elements
of $\mathbb{N}$ as vertices, and fix $\pi$. Thus, each
vertex $v$ in $G$ is mapped to a natural number $\pi(v)$,
such that $\pi[G]$ is an isomorphic copy of $G$ inside
$\Gamma$.
Let me now describe my finite neighborhood labels. Assign
to each vertex $v$ in $G$ any finite induced subgraph of
$G$ having size $\pi(v)$. (Note, $\pi(v)$ is a positive
natural number, so this is possible.)
The point now is that if I know the labels assigned to two
nodes, then in particular, I know the sizes of those
labels, and so I know which nodes inside $\Gamma$ they are
meant to correspond to, and so I know whether or not my
nodes should have an edge or not. Thus, from the labels I
can reconstruct the copy of $G$ inside $\Gamma$. QED
I anticipate that perhaps you will not like this proof,
because the reconstruction procedure I have given does not
using any of the edge information from the finite induced
subgraphs, but only the size of that subgraph, and perhaps
this seems like cheating. In this case, I think the
question would need to become more precise about what
exactly it is that is desired.
A: To clarify some questions (as I understand them) by an extended example:  Let $G_{a,b}$ be the directed graph with  $a+b+1$ vertices $-a,-a+1,-a+2,\cdots,-1,0,1,\cdots,b-1,b$ and edges directed away from $0$ (the root) and let $g_{a,b}$ be the corresponding unlabeled directed graph. Imagine that all the vertices are black. Then I can specify the root by showing you $g_{a,b}$ with the root colored red. If $a \ne b$ then I can specify any vertex of $G_{a,b}$ in this manner, otherwise not. If the values of $a$ and $b$ are known to us then I can specify the root by showing you $g_{1,1}$ with a red root. If $a \lt b$ then I can specify vertex $-j$ by merely showing you $g_{j,a+1}$ with a red point in the right place and vertex $j$ by something similar with $g_{a,c}$ where $c=\min(j,a+1)$. All this is true for $G_{a,\infty}$ with $a$ finite. 
For the undirected graph with paths of lengths $a+1,b+1,c+1$ sharing a common endpoint similar things are true when $a \ne b \ne c \ne a$. Would that be an undirected example of the desired type if $c=\infty?$
