MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 added 194 characters in body

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))\ \ \ (**)$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

ADDENDUM 1: Assume we define $Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$ where the $\phi_i(x)$ use the symbol $R$. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to $(**)$.

ADDENDUM 2: The "solutions" of the informal and sketchy "equation"

$$Rxy \equiv \neg(\exists x_1)...(\exists x_n) Rxx_1 \wedge ... \wedge Rx_ny$$

are exactly the trees.

3 added 410 characters in body

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property (*) $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert (*) $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$$phi_{m_i}(y))\ \ \ (**)$$This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued? ADDED: Assume we define Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y)) where the \phi_i(x) use the symbol R. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to (**). How do I have to think about this (kind of circular or impredicative definition)? 2 added 13 characters in body A different point of view: Consider asymmetric graphs. In such graphs every single node v_i can be uniquely described by a formula first order property (*) \phi_i(x) which holds iff x = v_i. For finite graphs you have Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i}) for a suitable set of pairs (v_{n_i}, v_{m_i}). Now insert (*) and you get$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

1