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.

I was thinking about 2-edge connected graphs, connected graphs that cannot be disconnected without removing at least two edges. I was thinking about a slight variant on this problem - what sorts of graphs are initially connected, connected after removing any one arbitrary edge, but guaranteed to be disconnected after removing any two arbitrary edges?

Any cycle graph with at least three nodes has this property, and I can't seem to think of any other graphs that would also have the same property. Are the cycle graphs with at least three nodes the only graphs that have this property? If so, how would I go about proving this? If not, is there another class of graphs with this same property?

Thanks!

share|improve this question
    
Yes. Hint: first characterize the (connected) graphs which are guaranteed to be disconnected after removing one arbitrary edge. –  Qiaochu Yuan Jul 27 '12 at 1:37
    
@QiaochuYuan- I'm aware that these graphs are all trees. One of the lines of attack I tried using here was to say "all graphs where deleting an arbitrary edge yield a tree," but I was having trouble showing that these graphs necessarily have to be cycles. Is that necessarily even true? And if so, any hints on how to proceed? –  templatetypedef Jul 27 '12 at 1:40
    
Yes, it's true. The main observation beyond that observation about trees is that a graph with the property you're interested in can't have a vertex of degree $1$, so "all paths can be continued." First find a cycle, then if there are any other edges follow the corresponding path until you arrive at the end of the rainbow (by which I mean a contradiction). –  Qiaochu Yuan Jul 27 '12 at 1:47
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.