Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have proved a certain result for all 2-connected graphs apart from those that fit the following criteria:

  1. They are "minimally 2-connected", that is, deleting any vertex will produce a graph which is no longer 2-connected, and

  2. They have circumference less than $\frac{n+2}{2}$, where $n$ is the number of vertices.

I have not been able to come up with an example of such a graph. Can anyone help?

Of course the best possible outcome would be that they do not exist!

share|improve this question
    
2-vertex-connected or 2-edge-connected? The former seems more likely, but I want to check. –  David Speyer Sep 7 '10 at 18:46
    
sorry...yes I mean 2-vertex-connected –  Adam Sep 7 '10 at 20:27
add comment

2 Answers

up vote 9 down vote accepted

There are lots of examples. For $t>5$, let $P_{1},..., P_{t}$ be internally disjoint paths with length $3$ such that each path has the vertices $x$ and $y$ as endpoints.

share|improve this answer
    
Thanks for the responses! David: yours is equally valid (and I assume posted at exactly the same time). I am only picking Shook's because it appears first. –  Adam Sep 7 '10 at 20:33
add comment

What if you take $5$ paths with $k$ vertices each and glue them together at the endpoints? So $5(k-2)+2=5k-7$ vertices in all, and circumference $2(k-1)=2k-2$.

share|improve this answer
add comment

Your Answer

 
discard

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

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