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

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?

share|cite|improve this question
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
up vote 4 down vote accepted

Fedja's comment definitely earns the grant. A minimal example is to let G be a star with four leaves {1,2,3,4}, let H be the bowtie obtained from G be adding the edges 13 and 24, and let H' be the wheel obtained from G by adding the cycle 1234.

share|cite|improve this answer
Thanks, I better accept an answer so this doesn't get listed as an open problem. – Douglas S. Stones May 21 '10 at 3:13

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.