# Is there a $6$ vertex planar graph which which has Eulerian path of length $9$?

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

1. If we connect two odd degrees vertices by an edge then those vertices have even degree and $G$ doesn't have Eulerian path.
2. 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.
3. 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.

• sorry but only now I realized that your answer was correct. thank you! – Yos May 25 '18 at 8:07

There it is. One regular hexagon plus equilateral triangle.

I cannot draw it now, but instead can give you the edge set $$E=\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{5},v_{5}v_{6},v_6v_1,v_{1}v_{3},v_{3}v_{5},v_{5}v_{1}\}.$$

• but it doesn't have Eulerian path because it has more than $2$ vertices of odd degree – Yos May 23 '18 at 14:47
• There is no odd degree. The hexagon has the equilateral triangle inside. So, there are vertices only of even degrees.4,4,4,2,2,2. – Taehee Ko May 23 '18 at 15:12
• can you please add the drawing I'm not sure we're thinking about the same – Yos May 23 '18 at 15:13
• @TaeheeKo Does your example really work? To any pair of vertices $u,v$ not already connected we can add an edge between them looping outside the hexagon. So the graph is still planar, no? – Jyrki Lahtonen May 24 '18 at 4:03
• I added a figure for the proposed graph. I agree with Jyrki Lahtonen that it has an Eulerean path of length $9$ but can stay planar with two more vertices connected. – Ross Millikan May 24 '18 at 4:32