8
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ 2-vertex-connected or 2-edge-connected? The former seems more likely, but I want to check. $\endgroup$
    – David E Speyer
    Commented Sep 7, 2010 at 18:46
  • $\begingroup$ sorry...yes I mean 2-vertex-connected $\endgroup$
    – Adam
    Commented Sep 7, 2010 at 20:27

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Adam
    Commented Sep 7, 2010 at 20:33
7
$\begingroup$

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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .