Proving properties of a simple undirected graph Given a connected simple undirected Graph (V,E), in which deg(v) is even for all v in V, I am to prove that for all e in E (V,E\{e}) is a connected graph. Intuitively I would say that the given properties lead to a graph that consists of one or more connected circles, but I have no idea how I would go about proving that.
 A: I don't think I could put it better than Daniel Fischer's comment:

In a connected graph, the sum of all the degrees of the vertices is even (each edge contributes two to the sum of the degrees). If the removal of an edge e disconnected the graph, the two components would both have an odd degree sum, because the degree of one vertex in each component were reduced by one.

But I might add some comments of my own:


*

*The deletion of an edge can only break a connected graph $G$ into $2$ components (assuming deleting the edge disconnects the graph).  Suppose edge $xy$ is deleted, and $v$ is a vertex.  Then there is at least one path from $v$ to $x$ in $G$.  If at least one of the paths does not path through $y$, then $v$ is connected to $x$ in $G \setminus \{xy\}$.  Otherwise, paths from $v$ to $x$ all pass through $y$.  So, $v$ is connected to $y$ in $G \setminus \{xy\}$.

*The "sum of all the degrees of the vertices is even" is a consequence of the Handshaking Lemma, and is true whether or not the graph is connected.

*For loop multigraphs (i.e., undirected graphs with loops and parallel edges)


*

*Assuming loops contribute $2$ to the degree of a vertex, then the Handshaking Lemma and the above argument hold, and the claim is still true.

*Assuming loops contribute $1$ to the degree of a vertex, then the result is false: for example, vertex set $\{1,2\}$, and edge set $\{11,12,22\}$.


*The result is not true for infinite graphs: for example, vertex set $\mathbb{Z}$, and edge set $\{i(i+1):i \in \mathbb{Z}\}$.
