Finding Connected Graphs That Do Not Model a V-Sentence Phi

[sara15]

how to define a V-sentence phi such that phi has aebitrarily large finite models and for any finite model G , G is a connected graph. after that to find a connected graph that does not model the sentence phi. please explain it to me.

 

[Office_Shredder]

You want to construct a first order statement about arbitrary vertices on a graph which, if it's true, gives a connected graph, and is not true for every connected graph.

Basically, the best way to approach this is to pick some classes of connected graphs (bipartite graphs, complete graphs, planar graphs, etc.) and see if you can find one which has a really easy characterization as a first order statement

 

[AKG]

how to define a V-sentence phi such that phi has aebitrarily large finite models and for any finite model G , G is a connected graph. after that to find a connected graph that does not model the sentence phi. please explain it to me.

This and the other two problems you posted look like homework. They should be posted in the homework section. When you post there, you should follow the guidelines there, which include showing your own work and not just asking other people to answer your questions. Also, as a general rule no matter where you post on the forum, you should use proper spelling and grammar, and define any special terms (e.g. what's a "V-sentence"?) so that it's easy for others to read.