# First order logic – each vertex of graph lies on some cycle

We consider only undirected graphs.
I would like to show that there exists sentence ϕ\phi in FOL such that G⊨ϕG\models \phi if only and only each vertex of GG lies on some cycle.

Problem for me is that this graph ma be infinite. When it comes to finite case it is easy to give ϕ\phi: ∀u∈Vdeg(u)≥2\forall_{u
\in V}\deg(u)\ge 2, what may be expressed in FOL. It is easy to show that every vertex (in finite graph) lies on some cycle only and only each vertex of the graph has degree at least 22.

However, I can’t deal with infinite graph. In particularity, ϕ\phi must be true both finite and infinite graphs. Of course if in infinite graph each vertex lies on some cycle then we can say that each vertex has degree at least 22.

I can’t prove that If in infinite graph each vertex has degree at least 22 t then each vertex lies on some cycle.

Can you help me ?

=================

What do you mean with “only and only if” (2nd line) and “only and only” (by the middle)? Is it “if and only if”? And wouldn’t graph-theory be a better tag? I suppose it would be very adequate…
– amrsa
yesterday

Yes, it means “if only and only” – I edited.
yesterday

=================