A maximal trail in a graph with exactly two odd vertexes

805 Views Asked by At

Let $G$ be a connected graph with exactly two odd vertexes, $u$ and $v$. Let $T$ be a maximal trail starting on $u$. Does it have necessarily maximum size? What can you say about a maximum trail starting on $u$?


I know that any graph with up to two odd vertexes has an Euler trail. Can I state that any maximal trail beggining on $u$ must be an Euler trail and finish on $v$?

1

There are 1 best solutions below

0
On

Let $w$ be the endvertex of $T$ distinct from $u$. Then $T$ have visited $w$ an odd number of times. If $w$ is distinct from $v$ then $w$ has even degree, so we could continue $T$ from $w$ along an unvisited edge, contradicting the maximality of $T$.

On the other hand, if both $u$ and $v$ have degree $1$ than no trail $T$ from $u$ to $v$ can be extended from its endpoints, but such a trail $T$ not necessarily is maximum, see the picture.

enter image description here