Q) I have to show that if every vertex in graph $G$ has an even degree , then $G$ has no bridge.
So by contradiction ,
If every vertex in graph $G$ has an even degree , then $G$ has a bridge , which means $G - e$ will result in a disconnected graph.
We know that in this graph, 1 vertex is adjacent to at least 2 other vertices.
So if we remove 1 edge from this graph , the vertices will still be connected resulting in a connected graph and $G$ will have atleast 1 vertex with an odd degree.(For eg , a graph with 4 vertices, each having an even degree , if we remove an edge , $G$ will still be connected .)
which makes my contradiction false.

Is this enough to prove this question or am I missing something ?

  • 2
    $\begingroup$ Please, try to make the titles of your questions more informative. You can find more tips for choosing a good title here. $\endgroup$ – Simply Beautiful Art Oct 5 '17 at 18:38
  • 1
    $\begingroup$ Indeed "Graph Theoryyyyy 1)" is by no means a good title. I have proposed one. $\endgroup$ – Jean Marie Oct 5 '17 at 18:42
  • $\begingroup$ @JMoravitz, One solution to the dilemma would be to improve the title oneself, and then upvote. $\endgroup$ – G Tony Jacobs Oct 5 '17 at 18:43
  • $\begingroup$ I apologize that my title wasn't informative and lame. :( @SimplyBeautifulArt $\endgroup$ – Johnathan Oct 5 '17 at 18:46

When beginning your proof by contradiction, what you should have rather than "If every vertex has even degree then $G$ has a bridge" is:

Suppose every vertex in $G$ has even degree and $G$ has a bridge.

We then look at what happens to the graph $G$ after having removed that bridge like you suggest. Unlike how you suggest though, removing the bridge will not have implied our graph will still be connected, it will be a disconnected graph and only a disconnected graph. Just because the ends of the removed bridge will be adjacent to something doesn't mean that the part of the graph on the one end of the bridge will be connected to the other part of the graph. We will in fact be guaranteed to be left with at least two separate connected components.

To continue, recognize that each connected component that used to be adjacent to the bridge should be able to form its own graph by itself.

Can you describe the degrees of the vertices in each of those connected components? For the one connected component, how many vertices of odd degree are there? Have you heard of something called the handshaking lemma? How might that be useful here?


Your proof is wrong in two ways:

  1. It isn't necessarily true that all vertices are connected to at least two others. A vertex could have no edges connected to it, because zero is an even number.

  2. You don't actually use the "even" property except to assert that each vertex has at least two edges. In fact, it is possible for every vertex in a graph $G$ to have at least two edges, and yet $G$ still has a bridge.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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