How do I prove this by contradiction?

A bridge in a connected graph is an edge whose removal disconnects the graph. Let $n \ge 1$.

Prove that a connected $2n$-regular graph has no bridges.

So far what I have is this:

Suppose for contradiction that a $2n$-regular graph has a bridge $uv$. By removing the edge $uv$, there is now $2$ connected graphs $A$ and $B$. Since $u,v$ has more than $2n$ vertices in the original graph, both $u$ and $v$ now have $2n -1$ vertex degrees.

The picture below is what I believe is a $2n$-regular graph

enter image description here

  • 1
    $\begingroup$ sweet yes that's a $2n$-regular graph. but you don't need it for you proof. So far you have two graphs let's call them $H$ and $J$ that are almost $2n$-regular, (because $\exists u\in V(H)$ s.t. the edges of $u$ or $deg(u)=2n-1$ same with $J$. Now what do you know about the total edges of a connected graph? $\endgroup$ – Sentinel135 Apr 13 '17 at 22:12
  • 1
    $\begingroup$ How so? All you did was remove one edge $uv$ for the graph to become disconnected. I.E. there is now two graphs now with one vertex where $deg(u)=deg(v)=2n-1$ all others are $2n$. Now for the edge $uv$ to have been a bridge $u$ and $v$ are in separate connected graphs in $G-uv$. So, the sum of each connected graphs would become odd. Which leads to a contradiction. $\endgroup$ – Sentinel135 Apr 13 '17 at 22:38
  • $\begingroup$ I do have an interesting question for you. What if you were trying to prove "An $n$-regular connected graph has no bridge for $n\ge 2$"? Could you prove that to be true? $\endgroup$ – Sentinel135 Apr 13 '17 at 22:51
  • $\begingroup$ Would it be same as my proof above, but with $4n$ replaced with $2n$. This would result in the handshaking lemma to be false since the vertex degree sum would be odd. $\endgroup$ – user3067059 Apr 14 '17 at 0:36
  • $\begingroup$ there would be a bit more than that. Yes you know that for any even-regular graph there is no branch, but what about odd-regular graphs greater than 1? You are right that you can use the first theorem of Graph theory, its just slightly tricky as to how that would be done. What if there is an odd amount of vertices in both $A$ and $B$? Can there be an odd amount of vertices in both? $\endgroup$ – Sentinel135 Apr 14 '17 at 1:17

Continuing from your attempt:
Consider graph $A$; this would contain vertices of degree $2n$ and one vertex - $u$ - of degree $2n{-}1$, summing to an odd number. However the total of vertex degrees in a graph (or a connected component) is required to be an even number as each edge is counted twice in summing the vertex degrees, and this is the contradiction as required.

Incidentally; while your illustration is undoubtedly 2-regular, it is not connected.

  • $\begingroup$ Wouldn't $v$ also have a degree of $2n-1$ as well? $\endgroup$ – user3067059 Apr 13 '17 at 22:38
  • 2
    $\begingroup$ If $v\in A$ then edge $uv$ wouldn't be a bridge. $\endgroup$ – Sentinel135 Apr 13 '17 at 22:41
  • 1
    $\begingroup$ Yep, and $v$ is in component $B$, so the same argument applies to that connected component also. Two contradictions for the price of one! $\endgroup$ – Joffan Apr 13 '17 at 22:42

All right with your approach. Just remember handshaking lemma.

  • $\begingroup$ Yep. Looks like we're on the same page here. Though I know it as the First Theorem of Graph theory. $\endgroup$ – Sentinel135 Apr 13 '17 at 22:22

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.