I need to prove that every graph containing only even vertices is bridgeless.

I understand that an even vertex is one with an even degree. Therefore an even vertex is one which is connected to an even number of vertices.

I also understand an edge $e = uv$ in a connected graph G whose removal creates a disconnected graph is a bridge.

I don't know how to use this to do the proof :(


Suppose that $e=uv$ is a bridge. When you remove $e$, you reduce the degrees of $u$ and $v$ by $1$ each, so if they were even to begin with, they’re odd in the disconnected graph $G-e$. Let $G_u$ be the component of $G-e$ that contains $u$. Get a contradiction by showing that the sum of the degrees of the vertices of $G_u$ is odd.

  • 1
    $\begingroup$ @BrianMScott in $G_u$ every vertex would have an even degree except for $u$ which will have an odd degree. This results in an odd degree sum which is a contradiction. Therefore the graph does not have any bridges. IE there is no edge we can remove which will create a disconnected graph. Is this fine? $\endgroup$ – sarah jamal Oct 8 '13 at 12:46
  • $\begingroup$ @sarah: That’s exactly right. $\endgroup$ – Brian M. Scott Oct 8 '13 at 12:49

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.