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.
Proving properties of a simple undirected graph
-
1In 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. – 2012-04-24
-
0Damn - 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. – 2012-04-24
1 Answers
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
edisconnected 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}\}$.