2 odd degree vertices - G admits a trail that visits all nodes

Question

I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems is:

Prove that if a connected graph G has 2 odd degree vertices, named x and y, then G admits a trail that visits all nodes.

I don't really know how to start it. What is the proof for that? Thank you very much!

Answer 1

It is easier to prove more:

Let $G$ be a connected graph with with exactly two nodes $x,y$ of odd degree. Then there exists a trail from $x$ to $y$ that visits all nodes and uses all edges.

We can prove the claim by induction on the number $e$ of edges, the case $e=0$ being vacuously true (because odd degree of $x$ implies that there is at least one edge).

Consider such a graph $G$ with $e\ge 1$ edges.

If $\deg x\ge3$, let $u,v,w$ be three distinct neighbours of $x$. At least two of them, $u$ and $v$, say, are $\ne y$. Consider $G'=G-\{xu\}$ and $G''=G-\{xv\}$. Both $G'$ and $G''$ have exactly two odd nodes, namely $y$ and $v$ or $y$ and $u$. If $G'$ is connected, we can apply the induction hypothesis to $G'$, find a trail in $G'$ from $u$ to $y$ through all nodes and using all edges of $G'$, prepend it with $xu$ and thereby obtain a solution for $G$. The same works if $G''$ is connected. Hence assume that neither $G'$ nor $G''$ is connected. Then $y$ and $v$ are in the same connected component of $G'$, and $y$ and $u$ are in the same connected component of $G''$ (because each component must have an even number of odd nodes), and in bot cases, $x$ is in another component. Hence there exists a walk in $G'$ from $u$ to $y$ not passing through $x$ and a walk in $G''$ from $y$ to $v$ not passing through $x$. We combine these to a walk in $G$ from $u$ to $v$ without passing through $x$. But then this walk, prepended with $xu$, shows that $G''$ is connected, contradiction.

We can perform a similar reduction if $\deg y>1$. Remains the case $\deg x=\deg y=1$. If there is an egde $xy$, this is all of $G$ and we are done. So assume otherwise and let $u\ne x$ be the unique neighbour of $x$. Let $G'$ be the graph obtained by removing edge $xu$ and node $x$. Then $G'$ is connected and has exactly two nodes $u,y$ of odd degree. Again, apply the induction hypothesis and prepend $xu$.