Graph splitting via an algorithm and proof of properties Given the following function:

function split(G)
    if (all vertices of G have even degree) then
        return (V (G), ∅)
    else  
        Let a ∈ V be a vertex of odd degree;
        S ← NG(a); 
        G ← G − a;
        for ((∀)u, v ∈ S, u != v) do
            if (uv ∈ E(G)) then 
                E(G) ← E(G) − uv; 
            else 
                E(G) ← E(G) ∪ uv;
        (W1, W2) ← split(G);
        if (|W1 ∩ S| % 2 = 0) then 
            V1 ← W1 ∪ {a}; 
            V2 ← W2;
        else 
            V2 ← W2 ∪ {a}; 
            V1 ← W1;
return (V1, V2)


I have to show that V1∩V2 = ∅, V1∪V2 = V(G) and the subgraphs of G obtained from V1 and V2 have an even degree on all vertices.

Now, based on the function it is obvious that the properties stated above hold true, but I am stumped as to how exactly should I go about proving them and by what general rule or criteria the split function splits the graph(I have no problem following the algorithm but the "big picture" escapes me).

EDIT: NG(a) Is the set of a's neighbours.
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.