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.

– Haskell Fun

yesterday

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

1 Answer

1

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

This isn’t true, by a compactness argument.

Suppose that φ\varphi be a sentence of first-order logic such that for every finite graph G,G, G⊨φG\models\varphi iff every vertex of GG lies on some cycle. We’ll show that this can’t be true also for every infinite graph.

Expand your language by adding a new constant symbol c,c, and consider the theory T={φ}∪{“c does not lie on a cycle of length exactly n”∣0

– Mitchell Spector

5 hours ago