Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a sentence $\chi$ in the language $L = \left\{E\right\}$ of graphs, where $E$ is a binary relation symbol (intended to be there is an edge between $x$ and $y$).

And let the graph axioms be so that a model is a symmetric graph with no loops.

The question is suppose we have an infinite graph $\Gamma$ such that $\Gamma \models \chi$ ( $\chi$ is true in $\Gamma$) is it necessarily true that there are infinitely many finite graphs in which $\chi$ is true?

I feel like the answer is probably, yes. Because for any sentence it seems like if I have a subgraph of $\Gamma$ which somehow contains all the elements I "need" for $\chi$ , it must also model the sentence. However, I have been unable to formalize this intuition so I'm no longer even sure if its correct.

Also note that this is homework, so I'd appreciate if possible people can help me to get to the correct solution rather than posting an entirely complete solution.

share|cite|improve this question
Is $E$ a two-place predicate $E(x,y)$ intended to be interpreted as xy is an edge? If not, exactly what is it? – Brian M. Scott Nov 10 '12 at 6:16
@BrianM.Scott Yes sorry, let me add that in. – Deven Ware Nov 10 '12 at 6:17
What does it mean for a graph to entail a sentence? – Dan Brumleve Nov 10 '12 at 6:18
@DanBrumleve I mean that the graph is a model of the sentence, or that the sentence is true in $\Gamma$ I will edit this also. – Deven Ware Nov 10 '12 at 6:20
@Dan: That notation means that $\Gamma$ is a model of the sentence. – Brian M. Scott Nov 10 '12 at 6:20
up vote 2 down vote accepted

Hint There is exactly one person who has only one neighbour. Everybody else has exactly two.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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