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.

-
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. –  Daniel Fischer Apr 24 '12 at 20:53
Damn - I didn't think it would be that simple. But yeah, now that you mention it... I just noticed we even have a Lemma with which this can be written even shorter. Thanks a lot, I really had a blockade on that one. –  Cubic Apr 24 '12 at 21:12

migrated from stackoverflow.comApr 25 '12 at 16:18

This question came from our site for professional and enthusiast programmers.

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.

• 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\}$.
• 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}\}$.