# Show non-definability of (biparted graphs, graphs with eulerian cycle, even number of nodes)

As you can see I am woring at three excercises:
Prove that following classes for graphs are non-definiable (on FO sentence):
a) biparted graphs
b) even number of nodes
c) graphs contains eulerian cycle

a) We know that biparted graphs can’t contain odd cycle. So lets $n$ will be number of rounds. Now, Let $A$ will be cycle (biparted graph) of length $2^{n}+2$ and $B$ will be cycle of length $2^n+1$. We know, that in $n$ rounds duplicator has winning stratrgy.
b) Similar apporach as in (a). Two chains of lenght $2^n+2$ and $2^n+1$.
c) This one seems to be the hardest. I think that we can give two structures for $n$ rounds:
$A$ is cycle of length $2^{n+1}$ and $B$ is chain of length $2^{n+1}$

Am I ok ?

### Hints

(a) Construct a set $S$ of axioms saying “$G$ is not bipartite and every vertex in $G$ has exactly two neighbours.” What graphs satisfy $S$? Now add a set $T$ of axioms that force $G$ to have no cycles, and use compactness on $S \cup T$.

(a*) Note that “$G$ is bipartite” is axiomatizable. Why? And where does the proof of (a) fail to show that it is not axiomatizable?

(b) Even implies finite. So following the same method described here leads to a proof.

(c) Eulerian cycle also implies finite. So same as (b).