0
$\begingroup$

Suppose that a graph $G$ has a bridge $xy$ such that the components of $G-xy$ are both Eulerian. Prove that G has an Eulerian path. What can you say about the beginning and end of the trail?

I understand intuitively why this must be true since if both the components are Eulerian then you can construct a Eulerian path of one of the components that ends at the bridge $xy$ and then construct a Eulerian path for the other component that starts at the bridge. Then a Eulerian path for $G$ would be constructed simply by crossing the bridge between the two separate Eulerian paths, but I have no idea how to formally prove it.

$\endgroup$
1
  • $\begingroup$ I think that's formal enough. If you want to describe it more formally, describe how you obtain an appropriate Eulerian path in each component (so that they end/start at the bridge) and maybe use some notation to describe the final path, and state how every edge is covered. For the question in the task, consider the degrees of vertices before and after removing the xy edge. $\endgroup$
    – Marcin Wrochna
    Commented Apr 4 at 13:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .