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