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


2 Answers 2


Take the graph below:

enter image description here

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.

  • $\begingroup$ sorry but only now I realized that your answer was correct. thank you! $\endgroup$
    – Yos
    May 25, 2018 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}\}.$$ enter image description here

  • $\begingroup$ but it doesn't have Eulerian path because it has more than $2$ vertices of odd degree $\endgroup$
    – Yos
    May 23, 2018 at 14:47
  • $\begingroup$ 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. $\endgroup$
    – Taehee Ko
    May 23, 2018 at 15:12
  • $\begingroup$ can you please add the drawing I'm not sure we're thinking about the same $\endgroup$
    – Yos
    May 23, 2018 at 15:13
  • 1
    $\begingroup$ @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? $\endgroup$ May 24, 2018 at 4:03
  • 2
    $\begingroup$ 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. $\endgroup$ May 24, 2018 at 4:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .