# Giving examples of two graphs satisfying two requirements.

We consider class of directed graphs (self edges (=loop) are allowed). The aim is: construct example of two graphs $G_1$ and $G_2$ such that:

1. for each graph $H$ with $\le 7$ nodes $G_1$ contains induced subgraph isomorphic to $H$ only and only if $G_2$ contains induced subgraph isomorphic to $H$.
2. Player $1$ (spojler) has winning strategy in Game with $7$ rounds.

To my eye, is is sufficient to give $K_8$ and $K_7$, but each node has loop (edge to self).

For the first point, we know that $K_8$ contains as subgraph $K_7$, so if $K_9$ has subgraph isomorphic to some $H=(V,_)$ such that $|V|\le 7$ so $K_8$ also.
If $K_8$ has subgraph isomorphic to some $H$ then we may say the same about $K_7$ because $H$ has at most $7$ nodes, we may close this $H$ in subgraph of $K_8$ which is simultatenously $K_7$.

For the second point. We know that in our $K_8$ each node has exactly $7$ distinct neighbours, however in $K_7$ each node has only $6$ distinct neighbours. So, after $7$ moves of player $1$ duplicator has no move. Simlpy, Player one choose any node of $K_8$ and then choose all its neighbours.

Tell me please, is it correct ? If not, how to fix it ?

• It is unclear to me how to reconstruct the Game that is being referred to in point 2. Please detail how this is a "first order sentence" as described in the title. – hardmath Nov 28 '16 at 12:07
• Ok, I did mistake in title. Edited. – user343207 Nov 28 '16 at 12:09
• It remains unclear what "Game" is referred to. Ideally the body of your Question ipresents a self-contained problem statement, plus of course the context of your thoughts about it (points of interest, request for help, etc.) . – hardmath Nov 28 '16 at 12:55

• @HaskellFun Now claim 1 fails for $G_1$ . . . – Noah Schweber Nov 29 '16 at 20:26