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?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.