1. ## Graph Theory problem

Let $G = (A \cup B, E)$ be a simple bipartite graph, such that $|A| = |B| = n$ and $|E| = e$ and such that for every vertex $v$ in the graph, $deg(v) = 2k+1$ for some $k \in \mathbb{N}$

Also, there is a closed path (the last vertex is the same as the first) of length $e+n$ that goes over every vertex in G at least once.

Prove that there is a perfect matching on G.

Pretty much at a loss on how I should do this. Any help is welcome.

I most likely need to use either Konig's theorem, or Hall's to solve this, but as I said I couldn't see where I could apply them.