## Examples of Ehrenfeucht-Fraïssé games. Winning Strategies.

Let us pick a very simple example in order to ilustrate the basic concepts of the EF game:
Let A and B be the graphs depicted below. A is a graph on two nodes a_{1} and a_{2}, and B consists of only one
vertex, denoted b.

Let us play 2 rounds of the EF game on A and B. The Spoiler starts the game, so he can choose any of the three nodes.
If the Spoiler chooses a_{1} or a_{2}, the the duplicator must pick a node in the graph B. Her only choice is
the node b. If the Spoiler chooses b, then the Duplicator must select from the other graph, so she can choose
either a_{1} or a_{2}. This is the complete list of possible moves for the two players in the first round.
Since the Duplicator makes her choice only after the Spoiler makes his, we can represent this succesion as a decision tree,
depicted below. Above the red line we can read the possible moves in the first round.

The Spoiler has a couple of wining strategies for the EF game on two rounds. One strategy is the following:

- In round 1, the Spoiler chooses a
_{1}. This forces the Duplicator to choose b.
- In round 2, the Spoiler chooses a
_{2}. This forces the Duplicator to choose b.

The Spoiler wins, because the map f from {a_{1}, a_{2}} to {b}, f(a_{1})=b and f(a_{2})=b
is not a partial isomorphism.

## Example 2:

Let us make the previous example a little bit more complicated, by considering the following graphs:

If we take a look at the two graphs, we realize that they are not the same. A has a chain of 6 nodes, whereas B has a chain of
7 nodes. The question is how big are the differences between the two graphs, or, in other words, how many rounds of the EF game
should we play in order for the Duplicator to loose?

One can easily see that the Duplicator has a winning strategy
for the 1-round and for the 2-rounds EF game on A and B. We will show that the
The Spoiler has a winning strategy for the 3-rounds EF game on A and B.

The spoiler starts by picking b_{4}
in the first round. b_{4} is a special node, because it represents the middle of the chain B.
According to how the Duplicator responds, the subsequent moves of the Spoiler are depicted below:

Each branch of the tree represents a possible succesion of moves of the Spoiler and the Duplicator.
Let us look on the branch (b_{4}, a_{3}, a_{1}, b_{1}, a_{2})
and see why the Spoiler wins.

- Round 1:
- the Spoiler chooses b
_{4}
- the Duplicator chooses a
_{3}
- so x
_{1} := a_{3} and y_{1} := b_{4}

- Round 2:
- the Spoiler chooses a
_{1}
- the Duplicator chooses b
_{1}
- so x
_{2} := a_{1} and y_{2} := b_{1}

- Round 3:
- the Spoiler chooses a
_{2}
- the Duplicator can choose anything from B, let us denote the chosen node by b
_{*}
- so x
_{3} := a_{2} and y_{3} := b_{*}

After the 3 rounds, we have X = {x_{1}, x_{2}, x_{3}}={a_{3}, a_{1}, a_{2}}
and Y = {y_{1}, y_{2}, y_{3}}={b_{4}, b_{1}, b_{*}}.

The map f from X to Y, f(a_{3}) = b_{4}, f(a_{1}) = b_{1}, f(a_{2}) = b_{*}
is not a partial isomorphism. It breaks the adjacency condition, as a_{2} is adjacent to both a_{1} and a_{3}
, whereas, whatever node the duplicator chooses in round 3 as b_{*}, it cannot be adjacent to both b_{1} and b_{4}.

The Spoiler has won by exploting the fact that in the graph B, b_{4} is 3 nodes away from the edges of the chain, whereas in the graph A
a_{3} is 2 nodes away from the left edge and 3 nodes away from the right edge.
The fact that the Spoiler played b_{4} in round 1 was very important.

## Example 3:

Let A and B be the graphs from the picture. We will show that the Duplicator has a winning strategy for the 2 rounds EF game
played on A and B.

Let us try to describe a winning strategy for the Duplicator:

- Round 1:
- the Spoiler can choose any node from A or B.
- if the Spoiler chooses from A, then the Duplicator will choose b
_{1};
else, the Duplicator chooses a_{1}.
- Let us assume that the Spoiler has chosen a
_{2}.
So after first round we can have x_{1} := a_{2}, y_{1} := b_{1}.

- Round 2:
- no matter what the Spoiler chooses, the Duplicator can mirror that.
Suppose for instance that this time, the Spoiler chooses a node from the graph B.
- If Spoiler chooses b
_{1} (same as y_{1} = b_{1}),
then the Duplicator must repeat its choice from round 1, and chooses a_{2}.
- If Spoiler chooses b
_{2} or b_{3}(nodes adjacent to y_{1} = b_{1}),
then the Duplicator must choose a node adjacent to x_{1} = a_{2}).

- So after the second round x
_{2} := a_{2} and y_{2} := b_{1},
or x_{2} := a_{1} and y_{2} := b_{2}/b_{3}.

- It is easy to check that in either case, the function f from X to Y is a partial isomorphism.

## Winning strategies:

A strategy for a player is a set of rules that describe exactly how that player should choose,
depending on how the two players have chosen at earlier moves.
A strategy for a player is said to be winning if that player wins every play in which he or she uses the strategy,
regardless of what the other player does. At most one of the players has a winning strategy (since otherwise the players
could play their winning strategies against each other, and both would win).
There is always a winning strategy for either the Spoiler or the Duplicator. As above, we write A ~_{n} B, if there is
a winning strategy for the Duplicator for the n-rounds EF games on the graphs A and B.

A winning strategy for the Spoiler can be described as follows:

- There is a possible move for the Spoiler such that

forall possible answer moves of the Duplicator

there is a possible move for the Spoiler such that

forall possible answer moves of the Duplicator

...

after n rounds, the Spoiler wins

A winning strategy for the Duplicator can be described as follows:

- Forall possible moves of the Spoiler

there is a possible answer move of the Duplicator such that

forall possible moves of the Spoiler

there is a possible answer move of the Duplicator such that

...

after n rounds, the Duplicator wins

One can easily remark that if the Duplicator has a winning strategy for the n rounds EF game,
then it also has a strategy for the k rounds EF game, where k is less then n.

## Exercises

**Exercise 1.** Let A and B be the graphs drown below.

- Prove that the Duplicator has a winning strategy for the 3 rounds EF game, that is A~
_{3}B.
- Prove that the Spoiler has a winning strategy for the 4 rounds EF game.