0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Feb 23 '17 at 22:37
  • $\begingroup$ 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. $\endgroup$ – Especially Lime Feb 24 '17 at 7:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Avi Tevet Feb 23 '17 at 8:28
  • $\begingroup$ @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. $\endgroup$ – Ofir Feb 24 '17 at 9:18
  • $\begingroup$ Ah, I see now. That is correct. $\endgroup$ – Avi Tevet Feb 24 '17 at 20:11
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Avi Tevet Feb 24 '17 at 20:16

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.