Tuesday, 26 August 2014

Does this graph exist?

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!

No comments:

Post a Comment