I'm stuck with a question:

Proof that you can't express if a graph is cyclic in first-order logic.

The definition of cyclic is that for every node there is a path back to the node wich never uses an edge twice.

This question appears in my book in the topic: Ehrenfeucht-Fraïssé games. For every $n \geq 0$ we need to find two graphs $G_1$ and $G_2$ so $G_1 \sim_n G_2$ such that $G_1$ is cyclic and $G_2$ isn't.

I can't find any two such finite graphs. However if I allow $G_2$ (right graph) to have an infinit amount of nodes the following two graphs work: enter image description here
Provided $G_1$ (left) has enough, but a finite amount of, nodes. But this doesn't seem verry elegant. I would like to see finite graphs wich also works.

Notice that the following strategy explains why a finite $G_2$ doesn't work:
round 1: spoiler choses an $a_1$ endpoint in $G_2$. Duplicator choses a point $b_1$.
round 2: spoiler choses the other endpoint $a_2$ in $G_2$. Duplicator choses a point $b_2$.
round 3: spoiler: neighbour point of $b_2$. Duplicator: neighbour point of $a_2$.
round 4: spoiler: other neighbour point of $b_2$. Duplicator is lost because there is no ohter neighbour point of $a_2$ because it's an endpoint in $G_2$

Thanks in advance.

  • $\begingroup$ I guess a line with $2^{n+1}$ nodes would suffice. $\endgroup$ – Primo Petri Aug 23 '15 at 9:53
  • 1
    $\begingroup$ Might be good to mention which book this is from. (Title, author(s), etc.) $\endgroup$ – user642796 Aug 23 '15 at 10:03
  • $\begingroup$ I have added to the question why a finite $G_2$ doesn't work. The book is a private book at our university wich isn't published. $\endgroup$ – abcdef Aug 23 '15 at 10:06
  • $\begingroup$ The proof with the infinite graph seems most elegant to me. $\endgroup$ – bof Aug 23 '15 at 10:57

Sorry, my previous answer was wrong because I misunderstood your definition of "cyclic". In this variant the answer is still yes, but you need another example:enter image description here

For given $n$, choose the number of "lollipops" to be very large and the distance between any two nodes of degree $>2$ to be very large as well. Then you cannot distinguish between the above graphs.

edit: a simpler example is possible as well, note that lines in this drawing correspond to paths of nodes. For given $n$ just make sure that distances between nodes of degree $3$ are very large: enter image description here

  • $\begingroup$ This is a nice example, I think it's gonna work with my interpretation of it. Thank you verry much. I will comment if something isn't clear to me. $\endgroup$ – abcdef Aug 23 '15 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.