Graph Theory

Q1) Use Euler's theorem to prove the following: Theorem 0.0.1. A connected graph G is semi-Eulerian (but not Eulerian) if and only if it has eractly two vertices of odd degree. Q3) Use Fleury's algorithm to find an Eulerian trail starting at u in the following graph: Show traces of work. Q4) Prove the following:2 Proposition 0.0.2. If every verter of a connected graph G has even degree, then it doesn't contain a bridge. Q5) The following represents the roadmap of an area that a postal worker needs to cover: Hint: Consider an auxiliary graph G obtained by joining the two odd degree vertices of G. Eulers theorem will now apply to G. The other direction can be proved using a similar construction Hint: If every vertex has even degree, then it has an Eulerian trail. Bu what happens once the trail goes through the bridge? The proof isn't very long. You could also delete a hypothetical bridge and use the trick at the end of the proof of Euler's theorem (with the Handshaking lemma.)