MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

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|cite|improve this answer

Your Answer


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.