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:

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 '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}\}.$$ 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 '18 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 '18 at 15:12
  • $\begingroup$ can you please add the drawing I'm not sure we're thinking about the same $\endgroup$ – Yos May 23 '18 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$ – Jyrki Lahtonen May 24 '18 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$ – Ross Millikan May 24 '18 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.