# A minimally 2-connected graph H and a 3-connected graph H' both contain G, does H' contain H?

Does there exists a connected graph G which is a subgraph of two graphs H and H' for which

• G, H and H' have the same vertex set,
• H is minimally 2-connected (i.e. deleting any edge from H makes is not 2-connected),
• H' is 3-connected and
• H is not a subgraph of H'?

I arrived at this question when thinking about how grant applications with "anti-terrorism" in the title seem to get much more funding than those without. I came out with this problem: A terrorist wants to disconnect G by deleting edges. To prepare for this attack, I want to add edges to G to make it 2-connected (i.e. H) at minimal cost, while at the same time preparing to make it 3-connected (i.e. H') at a later date. Does the choice of H matter?

-
Usually $k$-connected means "vertex $k$-connected" but if your hypothetical terrorists prefer cutting cables to blowing up relay stations, take a long path for $G$, make it into a single loop to get $H$ and add all edges except the edge that you used to get $H$ to get $H'$. Can I have my grant now? – fedja May 16 '10 at 0:02
Thanks... that was actually pretty easy. (: – Douglas S. Stones May 16 '10 at 1:14