Grouping vertices of a graph Suppose $G$ is a graph with $4n$ vertices. Prove that one can partition the vertices into two groups with $2n$ vertices, such that that there is an even amount of edges between the two groups.
How can one approach this problem? Induction doesn't seem to work and it is just so strange.
 A: For any graph $G(V,E)$ we have the handshaking lemma $\sum_{v\in V}d(v)=2|E|$, so the sum of vertex degrees is even. Therefore any graph must have an even number of vertices of odd degree.
Partition the vertices here into sets $A,B$ such that each set contains an even number of odd-degree vertices - for example, if there are $10$ odd-degree vertices, you could have $6$ in one part and $4$ in the other. If all vertices are of odd degree, you must have $2n$ odd-degree vertices in each part.
Then the sum of vertex degrees within each part will be even; in part $A$ (say) with degree sum $d_A$, the $f$ edges connecting within $A$ will contribute an even number $2f$ to that degree sum, and as a result there will be an even number of edges, $d_A{-}2f$, connecting outside the group.

Observations: We needed the graph to have $4n$ vertices so the partitions would each have an even number of vertices only for the case where every single vertex was of odd degree. If not every vertex has odd degree, the equal split will work for any graph with an even number of vertices. For a graph with an odd number of vertices ($2m{+}1$), there must be a vertex of even degree, so it will always be possible to partition the vertices into two groups that differ in number by one ($m,m{+}1$) and have an even number of edges connecting the two parts.
A: Make a partition $A,B,C,D$ of all vertices, so that $|A|=|B|=|C|=|D|=n$.
Now let the number of edges between

*

*$A$ and $B$ be $a$,

*$B$ and $C$ be $b$,

*$C$ and $D$ be $c$,

*$D$ and $A$ be $d$,

*$A$ and $C$ be $e$,

*$B$ and $D$ be $f$.

So the number of edges between $A\cup B$ and $C\cup D$ is  $$b+d+e+f =:p_1 $$
the number of edges between $A\cup D$ and $C\cup B$ is  $$a+c+e+f=:p_2$$
and the number of edges between $A\cup C$ and $B\cup D$ is $$a+b+c+d=:p_3$$
Now suppose the statment doesn't hold. Then all those sums $p_1,p_2,p_3$ must be odd and thus their sum $p_1+p_2+p_3$ is odd. But this is equal to $$2a+2b+2c+2d+2e+2f$$ which is even. A contradicton, so the statment does hold.
