# If $G$ is an Eulerian graph with edges $a$, $b$ sharing a vertex $v$, is it true that $G$ has an Eulerian trail in which $a$, $b$ are consecutive?

If $G$ is an Eulerian graph with edges $a$, $b$ sharing a vertex $v$, is it true that $G$ has an Eulerian trail in which $a$, $b$ are consecutive? Give a proof if it's true,and provide a counterexample if it's false

My intuition is that this is true and I tried to prove it by contradiction.

Assume if $G$ is an Eulerian graph with edges $a$, $b$ sharing a vertex $v$, the $G$ does not have an Eulerian trail in which $a$, $b$ are consecutive.

I don't really know how to proceed next. A property of Eulerian graph is that all the vertices have even degree. Can I use this to proceed with the proof? Thanks for any help.

As Ofir says, this is not true. A good way to try to approach this problem would be to say that $G$ has an Euler trail in using the edges $xy$ and $yz$ consecutively if and only if there is a trail in $G-\{xy,yz\}$ which starts at $x$ and finishes at $z$, and covers all the edges. Such a trail exists if and only if $G-\{xy,yz\}$ has $d(x),d(z)$ odd and all other degrees even, and is connected. The first condition will always hold ($G$ has all degrees even, and by removing those two edges we change $d(x),d(z)$ by $1$ and $d(y)$ by $2$), but the second condition need not hold, and Ofir gives an example where it doesn't.

So what you can say is that $G$ has an Euler trail in using the edges $xy$ and $yz$ consecutively if and only if removing those two edges leaves a connected graph.

• If removing $xy$ and $yz$ isolates $y$, then such a trail exists (then in fact all Eulerian trails have these two edges consecutive). The subgraph consisting of the edges and the non-isolated vertices needs to be connected. – Daniel Fischer Feb 23 '17 at 22:37
• Yes, you're right, the condition for a graph with even degrees to be Eulerian is that all edges are in one component, which is not quite the same as being connected. – Especially Lime Feb 24 '17 at 7:04

This is not true. For example take a graph which is two cycles and glue them together on a single vertex (namely the number 8), or more specifically the graph

a-b-c-a-d-e-a

There is basically only one Eulerian cycle and in it you cannot travel by c-a-b, because then you will close one cycle and you cannot reach the second one.

• But you are kind of proving the opposite, that in G where v connects to a & b, there exists an Eulerian path which does not traverse a & b consecutively. I think the proposition is that in any graph G where v connects to a & b, there exists a path which traverses a & b consecutively. – Avi Tevet Feb 23 '17 at 8:28
• @AviTevet The question was given a graph G with v connected to two edges $e_1,e_2$, can I always find an Eulerian path such that $e_1,e_2$ are consecutive edges. This is not true, and I proved it by giving a counter example - in my example you don't have any Eulerian path such that c-a is followed by a-b. – Ofir Feb 24 '17 at 9:18
• Ah, I see now. That is correct. – Avi Tevet Feb 24 '17 at 20:11

I believe the opposite of the accepted answer, namely that the proposition is true. To find an Eulerian path where a and b are consecutive, simply start at a's other side (the one not connected to v), then traverse a then b, then complete the Eulerian path. This can be done because in an Eulerian graph, any node may start an Eulerian path. Thus, G has an Eulerian path in which a & b are consecutive.

I think a counterexample to disprove this proposition must prove provide an example graph G with v connected to a and b for which no Eulerian path can be found having a and b consecutive.

• Followup: translating @ofir's counterexample to these terms means that in the graph v-a-b-v-c-d-v, there is no Eulerian path where a-v is followed by v-b. This is a valid counterexample and disproves the proposition. – Avi Tevet Feb 24 '17 at 20:16