A class of "minimally 2-vertex-connected graphs" - that is, 2-vertex-connected graphs which have the property that removing any one vertex (and all incident edges) renders the graph no longer 2-connected - have come up in my research.

Dirac wrote a paper on "minimally 2-connected graphs" (G. A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967),. 204-216), which gives quite a detailed description of the structure of such graphs. However, in his sense, minimal 2-connectivity means that deleting any EDGE leaves a graph which is not 2-connected, which is not an equivalent property to the vertex-deletion one. Does anyone know anything about graphs with the latter property?

In the hope of stimulating some discussion, here is a wildly speculative and vague conjecture: The only graphs satisfying this property are simple cycles, and certain cycles with chords.


Here is a more general family:

Draw your favorite tree in the plane, with circles for the nodes and "thick" lines for the edges. Now turn every circle into a cycle, and every thick line into a pair of parallel paths $p_1, \ldots, p_m$ and $q_1, \ldots, q_n$ with various crossbraces. The crossbraces just have to follow the rule that if $p_i$ is connected to $q_\ell$ and $p_j$ is connected to $q_k$, for $i<j$ and $k<\ell$, then $j =i+1$ or $\ell=k+1$.

This is probably still not close to a complete characterization, but at least shows that the class is a lot broader than the small class you posited to promote discussion.


As the edited question mentions, Dirac did something similar, although minimality is with respect to edge deletion while connectivity is with respect to vertices (hence some confustion arose) The link is here.

I will mention that Chaty and Chein (1979) solved the problem where minimality is with respect to edge deletion, and connectivity is with respect to edges.

Also, I don't think that all such graphs are cycles with some chords, since subdividing any edge of a minimally 2-connected graph preserves minimal 2-connectivity. So, I can certainly destroy a chord by subdividing it.

  • 2
    $\begingroup$ Regarding "subdividing any edge of a minimally 2-connected graph preserves minimal 2-connectivity": Consider a cycle with one chord $(u,v)$. Then subdivide the chord: add a new node $t$ and replace $(u,v)$ with the path $(u,t,v)$. The resulting graph is no longer minimally 2-connected: you can remove the node $t$ and you are left with a cycle which is 2-connected. However, if you add two nodes $s$ and $t$ and replace $(u,v)$ with the path $(u,s,t,v)$, then I think the new graph is minimally 2-connected (provided that in the cycle the distance between $u$ and $v$ is at least 3). $\endgroup$ – Jukka Suomela Aug 14 '10 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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