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$.