Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

migrated from stackoverflow.com Apr 25 '12 at 16:18

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

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.