Using Ehrenfeucht-Fraisse to show that two graphs are distinguishable

126 Views Asked by At

We have two structures $A$: an infinite clique and $B_n$ and a clique of size $n+1$.
To my eye, duplicator has winning strategy in game with $n$ rounds. Simply, duplicator copies moves of spoiler. It is possible, after each move - newly chosen vertex has the same number of related (chosen before) verticles.

However, Is it possible. I think that I can't see something wrong in my reasoning.

1

There are 1 best solutions below

1
On BEST ANSWER

Your reasoning is sound. Indeed, no matter what vertices are chosen by either player, after $k$ rounds, both graphs will be cliques of size $k$, hence order isomorphic.