Property of a connected graph with even no. of vertices Let $G$ be a connected graph with an even number of vertices. Prove that you can select a subset of edges of $G$ such that each vertex is incident to an odd number of selected edges.
I am thinking induction is a possible way out but I have no idea if it really works or not.
 A: Since the sum of degrees of vertices in $G$ must be even, then $G$ has even number of vertices with odd degree. Also, since number of vertices in $G$ is even, there is an even number of vertices with even degree.
Consider a shortest path whose endpoints are vertices with even degree. Clearly, this path exists because $G$ is connected. Let this path be $P=v_1 v_2 \ldots v_l$. $v_1$ and $v_l$ have even degree, and rest of the vertices in this path have odd degree, because if some $v_x \in P$ for $2 \le x \le l-1$ has even degree, path $v_1 v_2\ldots v_x$ would have shorter length than path $P$, and it’s endpoints would have even degree, but this is a contradiction since $P$ is shortest path with this property.
Now, we apply following algorithm so that vertices $v_1$ and $v_l$ become vertices with odd degree, and rest of them stay with odd degree. First, we remove edge $v_1 v_2$. $v_1$ now has odd degree, $v_2$ has even degree. Then, we remove edge $v_2 v_3$. $v_2$ now has odd degree, but $v_3$ has even degree.
We continue this algorithm; more precisely, we remove edges $v_i v_{i+1}$ for $1 \le i \le l-2$ in this order, and we get in situation where only $v_{l-1}$ and $v_l$ have even degree in path $P$. Finally, remove edge $v_{l-1} v_l$ and they both become vertices with odd degree.
Now, all vertices in path P have odd degree. We decreased total number of vertices with even degree by two. We repeat this algorithm (find a shortest path whose endpoints are vertices of even degree and then apply described algorithm to change parity of endpoints ) until number of vertices with even degree becomes $0$, and it will, because we said that totally there is even number of these vertices, and in every step, we change parity of two of them. This completes the proof.
A: For each subset $A\subseteq E$, let $f(A)\subseteq V$ be the set of vertices of $G$ that are incident with an odd number of edges in $A$.  Note that $|f(A)|$ is always even (per hand-shaking). As $|V|$ is even, $|V\setminus f(A)|$ is also even.
Pick a set $A$ that maximizes $|f(A)|$. If $f(A)\ne V$, there exist at least two vertices $v,w\in V\setminus f(A)$. As $G$ is connected, there is a path from $v$ to $w$. Let $A'$ be the symmetric difference of $A$ and the edges in this path. Then $f(A')=f(A)\cup \{v,w\}$, contradicting maximality. We conclude $f(A)=V$.

A variation to the above theme:
Group the vertices of $G$ into disjoint pairs.
For each such pair $(v,w)$, pick a path from $v$ to $w$.
Let $A$ be the set of edges that are used in an odd number of these paths. Verify that this does the trick.
