Let G be a connected graph of order n>= 3 without bridges. Suppose that for every edge e of G, each edge of G - e is a bridge. What is G? Justify your answer.

My answer: G is a cycle graph Cn. Given G:u=v0,v1,...,vn,v0=u (a cycle graph) with n?3, there are no bridges. However, when you remove any edge e=uv, you are left with G?e:u=v0,v1,...,vn which is just a path graph of order n in which every edge e is a bridge.

I have half the question answered I just need to figure out the converse? That is, show that if G is not Cn, then either G has a bridge or there are edges e and f such that f is not a bridge of G?e.

 

Answer rating: 100% (QA)

suppose we have a graph Cn Gs a free thew it must Contain abridge ... View the full answer