## Description of the Ehrenfeucht-Fraïssé games

In the EF game, there are two players, called the Spoiler, and the Duplicator. The board of the game consists of two graphs,
let us denote them by A and B. The goal of the Spoiler is to show that the two graphs are different; the goal of the
duplicator is to show that they are the same.

The players play a certain number of rounds. Each round consists of the following steps:

- 1. The Spoiler picks either graph A or graph B.
- 2. The selects makes a move. He chooses a vertex from that graph.
- 3. The Duplicator goes next. She responds by picking a vertex from the other graph(the graph that the Spoiler did not select from).
- We denote by x
_{i} the vertex selected from A, and by y_{i} the vertex selected from B in this i-th round
of the game, regardless of who has selected them.

Let us denote by X = {x

_{1}, x

_{2}, ... ,x

_{n}}, and by Y the set
Y = {y

_{1}, y

_{2}, ... ,y

_{n}}.

The Duplicator wins the n rounds EF games on the graphs A and B if
the map f from X to
Y, f(x

_{i}) = y

_{i}, i = 1,...,n preserves adjacency and equality. This means that:

- x
_{i}, x_{j} are adjacent
in A if and only if y_{i}, y_{j} are adjacent in B.
- x
_{i} = x_{j} if and only if
y_{i} = y_{j}.

In this case, we call the map f

*a partial isomorphism* of the two graphs A and B, and we write A ~

_{n} B.

Otherwise the Spoiler wins the n rounds EF game on the graphs A and B.

Intuitively speaking, the Duplicator wins the n rounds game if she can duplicate any n moves
that the Spoiler makes. So the n rounds EF game cannot distinguish between A and B. In this case, we write A ~

_{n} B.
Otherwise the Spoiler wins the n rounds EF game on the graphs A and B.

## Observations:

- The Spoiler decides in the beginning of each round which graph to choose from. Its choice may change from round to round.
- If both graphs A and B have more then n vertices, in the n-rounds EF game, there is no point for the Spoiler to repeat his choices.
For instance, if in the j-th round, the Spoiler selects a vertex x
_{j}
equal to a previous x_{i} that he selected in the i-th round, then the Duplicator can repeat her choices as well.

She can simply select y_{j} = y_{i}.