Let $G$ be a graph of odd order. Prove that there exists a non-empty vertex subset $U$ of $G$ such that each vertex in $G$ has an even number of neighbors in $U$.
Here are all the graphs on five vertices that are neither disconnected nor trees which are either trivial or not very difficult to find. (There are likely some mistakes, for instance $G_{16}$ should also have its top vertex shaded.) There is no discernable pattern that I can spot. Sometimes it is all of the vertices with even degree, sometimes it is all of the vertices with odd degree, and sometimes neither of those work.
An induction proof is theoretically possible. If the graph is empty, then the solution is trivial. Otherwise we could take some edge $uv$ and consider the graph induced by the vertex set $V\setminus\{u,v\}$. That would have a solution by our induction hypothesis. But how that could be transformed to a solution for $G$ is not intuitively obvious.
Let $n$ be the (odd) order of $G$ and $A$ the adjacency matrix associated to $G$. You seek a nonzero solution to $A\vec{x} = \vec{0}$ in $\mathbb{F}_2^n$. It suffices to show that the determinant of $A$ is even.
Let $S = (\epsilon_{i,j} a_{i,j})_{1 \le i,j \le n}$, where $\epsilon_{i,j} = -1$ if $i < j$ and $\epsilon_{i,j} = 1$ otherwise. Then $\det(S) = \det(S^T) = \det(-S) = (-1)^n\det(S) = -\det(S)$, so $\det(S) = 0$.
Finally, observe that $S = A$ in $\mathbb{F}_2$, so $0 \equiv \det(S) \equiv \det(A) \pmod{2}$, as desired.