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
1
$\begingroup$
graph-theory
-
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