Prove G is bipartite, which implies it has no odd Eulerian cycles. Using contradiction obviously means we start with the assumption that it can have cycles of odd length. From there, what should I think about?