Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd number of these edges.
First observation is that once you have selected a set $E$, the unselected edges don't really matter much. They only matter because we need the graph to be connected. So, we can remove a number of edges of this graph until we get a tree. If we can create a set $E$ using the edges of this tree satisfying the required conditions, then this $E$ will also satisfy the conditions for the original graph.
So, to simplify things, assume we have a tree with an even number of vertices. This tree must have leaves. It is necessary that $E$ must contain the edges incident with these leaves.
Now I am stuck. Ideas that I've had include strong induction, colouring etc..
How do I proceed?
Thanks
Best Answer
You would like to prove a connected graph with an even number of vertices has a subgraph in which every vertex has odd order. In fact much more is true.
We call a parity designation $\sigma$ of $G$ a function that assigns to each vertex $v$ of $G$ a desired parity for its degree(odd or even), with the only restriction that there is an even number of vertices with odd desired parity.
We prove that given a parity designation $\sigma$ of $G$ there is a spanning subgraph of $G$ that satisfies that parity designation. We prove it by induction and via the use of spanning substrees.
Base case: If $G$ has $2$ vertices and connected then $G$ is $K_2$ and there are only two possible parity designations (even, even and odd,odd). It is easy to see they are satisfied by the subgraph with no edges and by $K_2$ itself.
Inductive step. $G$ has $n+1$ vertices . Since $G$ is connected it has a spanning subtree $T$. This tree has a leaf $v$. Notice that when we romve $v$ from $T$ the remaining graph is still connected, therefore when we remove $v$ from $G$ we obtain a connected graph $G'$ with $n$ vertices.
Case $1$: The parity designation $\varphi$ requires that $v$ is an even vertex. This is the "easy" case. Consider $\varphi$ restricted to $G'$. This is a parity designation (because $v$ is supposed to be even, so there is still an even number of vertices in $G'$ that should be odd). By induction there is a spanning subgraph $H'$ of $G'$ that satisfied $\varphi$ in $G'$. Notice the edge of $H'$ also satisfy $\varphi$ in $G'$ since they leave $v$ with degree $0$ which is even as desired.
Case $2$: The parity designation $\varphi$ requires that $v$ is an odd vertex. In this case let $w$ be the only neigbour of $v$ in the spanning subtree $T$. We define $\varphi'$, which is going to be a parity designation for $G'=G-v$. We let $\varphi'$ be equal to $\varphi$ for every value except $w$. In $w$ $\varphi'$ is going to be the opposite of $\varphi$ so if it was odd we cahnge it to even and if it was even we change it to odd. By induction there is a subgraph $H'$ of $G'$ that satisifies $\varphi'$. If we take the edges of $H'$ together with $wv$ we obtain a spanning subgraph of $G$ that satisfies $\varphi$. It is clear that it satisfies $\varphi$ for all values other than $u$ and $v$ since $\varphi'=\varphi$ in these values. In $u$ it also holds because without edge $uv$ the degree was the opposite of what $\varphi$ indicated, however after adding edge $uv$ it is the same as $\varphi$. $w$ also has the desired parity since the order of $w$ is $1$,which is odd.
What we have just proven implies what you want, just let $\varphi$ be the parity designation that asks for every vertex to be odd.(Notice this is a parity designation since the order of $G$ is even).
Second solution:
$G$ has an even number of vertices of odd order and hence $G$ has an even number of vertices of even order (Since there is an even number of vertices).We shall remove some of the edges of $G$ until every vertex has odd order. The strategy wel will use is the following: Split the vertices of even order into pairs. Let the pairs be $a1,b1$ and $a_2,b_2\dots a_k,b_k$ we will start adding and removing vertices until every vertex is odd. We start by making $a_1$ and $b_1$ odd (without changing the others). Because $G$ is connected we can find a path between $a_1$ and $b_1$.
Remove all of those edges, doing this makes $a_1$ and $b_1$ have odd degree (since their degree is reduced by $1$) and leaves evry other edge with the same parity(since the other affected vertices have their degree reduced by exactly $2$). The next thing we do is make $a_2$ and $b_2$ odd (without changing the others). Take the path between $a_2$ and $b_2$ and now what we do is slightly different, for each edge in the path there are two options, if the edge was removed previously, put it back in, if it was not removed then remove it). This process makes $a_2$ and $b_2$ odd since the degree of each vertex either increased by $1$ or decreased by $1$. On the other hand all other vertices stay with the same parity.
That is beacuse it can increase by $2$ (If the edges on both sides of the vertex were added back in) It can stay the same (if one edge was removed and the other was added back in) or it can decrease by two (if both edges where removed). We then proceed to making $a_3$ and $b_3$ both odd by using the same approach as for $a_2$ and $b_2$. We then make $a_4$ and $b_4$ odd and so on until we make $a_k$ and $b_k$ both odd. When we do this we will be finished.