Теория графов, дискретная математика

Question

Дана компонента реберной двусвязности в неориентированном графе. Доказать, что для любой пары вершин a, b и какого-то ребра (u-v) из этой компоненты существует путь a - . - u - v - . - b, проходящий по каждому ребра графа не боле чем один раз. Интуитивно хочется в это верить, но желательно было бы формальное доказательство.

Answer 1

я так понимаю, что для каждой пары вершин есть пара реберно непересекающихся путей:
P1 (a, u) , P2 (a, u)
P1 (a, v) , P2 (a, v)
P1 (u, b) , P2 (u, b)
P1 (v, b) , P2 (v, b)

пусть ребро (u-v) не принадлежит ни одному из этих путей.
тогда искомый путь строится элементарно: P1 (a, u) U (u-v) U P1 (v, b)

пусть ребро (u-v) принадлежит, например, пути P1 (a, u) и не принадлежит ни одному пути из u в b.
тогда искомый путь может быть, например, таким:
P1 (a, u) U P1 (u, b)

пусть ребро (u-v) принадлежит, например, пути P1 (a, u) и принадлежит пути P1 (u, b) .
значит, ребро не принадлежит пути P2 (a, u) , и искомый путь будет такой:
P2 (a, u) U P1 (u, b)

ну и всё. остальные варианты сводятся к этим трём с точностью до переобозначений, если не путаю.