Graph splitting via an algorithm and proof of properties
I'll give you the schema of the proof. You'll have to fill in the blanks on your own. The idea is to prove by induction the following property $P(n)$:


  On a graph $G$ having $n$ vertices, the function $\mathrm{split}(G)$ terminates and returns a partition $V_1,V_2$ of the vertex set of $V$ such that in the subgraphs of $G$ induced by $V_1$ and $V_2$, all vertices have even degree.


First you have to prove the base case $P(1)$. That's quite easy.

Now, for every $n$ you have to prove that $P(n)$ implies $P(n+1)$. To do this, you analyze what happens when $\mathrm{split}$ is run on a graph $G$ having $n+1$ vertices. There are two cases: if all degrees in $G$ are even then it is easy to see that $\mathrm{split}(G)$ terminates with an appropriate partition. Otherwise, $\mathrm{split}$ creates a graph $G'$ on $n$ vertices and runs itself on $G'$. Since $G'$ has $n$ vertices, the induction hypothesis implies that $\mathrm{split}(G')$ with a partition $V'_1,V'_2$ of the vertex set of $G'$ such that the subgraphs of $G'$ induced by $V'_1,V'_2$ have only even degrees. The procedure $\mathrm{split}$ uses $V'_1,V'_2$ to create a partition $V_1,V_2$ of the graph $G$. It thus clearly terminates. To finish the proof, you have to show that the subgraphs of $G$ induced by $V_1,V_2$ have all even degrees.

This is the structure of the proof. All you have to do now is to fill in the blanks.