Euler tour is a cycle that traverses every edge in a graph exactly once, and finishes at the same vertex where it started. In this problem we will complete steps to show the following theorem:

5. Recall from lecture that an Euler tour is a cycle that traverses every edge in a graph exactly once, and finishes at the same vertex where it started. In this problem we will complete steps to show the following theorem: A connected graph has an Euler tour if and only if every vertex has even degree (a) Give a direct proof of the following: If a connected graph has an Euler tour, then every vertex has even degree. (b) Now we step through showing that if every vertex has even degree, then the connected graph has an Euler tour. Let's consider the longest path in the graph that does not traverse any edge more than once, L i. Why must L exist? ii. Why must L be a cycle? ii. Why must L include all edges incident to the starting/ending vertex? iv. Prove by contradication the L must be Eulerian, i.e. L must include all the edges in the graph. (Why does this complete the proof?)