In this answer on cstheory, David Eppstein explains how to reduce an instance of the minimum-weight edge cover problem to a maximum-weight matching:
[Given a minimum-weight edge cover,] if we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w_e$ be the weight of $e$, then the cost of a solution is $$\sum_{v\in G} c_v + \sum_{(u,v)\in M} (w_{(u,v)}-c_u-c_v).$$ The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c_u+c_v-w_{(u,v)}$.
This reduces the problem to finding a maximum-weight matching with the revised weights (the remaining edges in the cover are chosen greedily as described above); this can be found using, for example, the Hungarian algorithm with runtime $O(V^2E)$.
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.
Best Answer
Since $G$ is connected, it has a spanning tree. You can delete any leaf $v$ from the spanning tree and the graph still has a spanning tree, so is still connected.