All graphs considered are undirected and have a finite number of edges. The
degree of a node is defined as the number of edges that connect that node to
a different one plus twice the number of self-loops (i.e. edges connecting a
node to itself) on that node. We are asked to prove that, for all graphs,
relation R given by

  (R) The number of nodes of odd degree is even

holds.

We first observe that it trivially holds for all graphs with no edges,
because, if there are any nodes at all, their degree could only be 0, which is
even. Therefore, the number of nodes of odd degree is even simply because
there are not any such nodes.

Next, we observe that in any graph with at least one edge, removal of an edge
leaves the parity of the number of nodes of odd degree invariant.

Proof: Removal of an edge changes only the degree of the nodes that constitute
its endpoints, and not of any others. If the removed edge is a self-loop, the
degree of the node decreases by an even number, namely 2, thereby maintaining
the parity of its degree and therefore the total number of nodes of odd and
even degree in the graph remains the same. If, on the other hand, the removed
edge connects two different nodes, we observe that the removal of that edge
will invert the parities of the degrees of those two nodes (because the degree
of each will be decreased by 1). Now, if the degrees of the two nodes are of
the same parity, the number of nodes of odd degree will change by an even
number, namely 2; otherwise, if the degrees of the two nodes are of opposite
parities, then the degree of the one will become even while that of the other
will become odd, therefore the total number of nodes of odd degree will remain
the same. Observing that removal of an edge can only change the total number
of nodes of odd degree by an even number, namely either 2 or 0, we conclude
that the parity of that number remains invariant. (End of Proof.)

Because the parity of the number of nodes of odd degree is invariant under
edge removal, it follows that R itself is invariant under that operation.

Now, because one may take any graph and remove its edges one by one until it
yields an edge-less graph, and because R holds for any edge-less graph and is
furthermore kept invariant under edge removal, the truth of R for an edge-less
graph equivales to its truth for the original graph, hence R holds for the
original graph and therefore for all graphs.

Q.E.D.