Let $G$ be a simple graph with Eulerian path of length $9$. There're two non-adjacent vertices $u, v$ in $G$ and if we connect $u$ and $v$ by an edge $G$ is not planar anymore. Does such a graph exist over $5$ and $6$ vertices?
I think it doesn't exist in both cases. If there're $5$ vertices then because $G$ has Eulerian path it must have $2$ vertices of odd degree. In our case they can be only of degree $3$ or $1$.
- If we connect two odd degrees vertices by an edge then those vertices have even degree and $G$ doesn't have Eulerian path.
- If we connect two even degree vertices with an edge then their degrees become then there're more than two odd degree vertices and $G$ doesn't have Eulerian path.
- If we connect an odd degree vertex to even degree then it's OK but there're not enough vertices such that this connection will render $G$ not planar (I don't know how to prove this).
From drawing such graphs for both $5$ and $6$ vertices I think it's impossible to satisfy the conditions but I'm not sure how to finish the proof. By intuition I see that if there're $5$ vertices there're not enough vertices so that there're $u$ and $v$ which will cause $G$ be not planar.
And when there're $6$ vertices then there're not enough edges so that the length of Eulerian path is $9$.
Take the graph below:
It contains an Eulerian path: for example, $a,d,f,c,d,e,f,a,b,c$.
It's planar. I drew it with a crossing, because I'm lazy, but we can draw the edge $ad$ outside the hexagon instead, and then we have a plane embedding.
If the edge $be$ is added, the resulting graph is no longer planar. In fact, the resulting graph contains $K_{3,3}$ as a subgraph, with $\{a,c,e\}$ on one side and $\{b,d,f\}$ on the other.
Contracting edge $ab$ gives us a $5$-vertex example which has already been mentioned in another answer.