Graph $G$ is 2-connected. It means that for each two edges there are exists at least to disjont (in terms of edges) paths.

Graph $G$ is not directed.
Our task is to find spanning subgraph $H$ of graph $G=(V,E)$ such that $H = (V, F)$ such that $F=O(|V|)$ and $H$ is 2-connected.

So far I have came up with some idea, but I have not proved it.

Let execute DFS in order to get DFS search tree. Now we will get every edge from this tree - then $H$ is spanning of $G$.
Additionally for each node in this tree we add back edges $e$ such that $e$ jump possibly high.

What about this idea ? Could you give me hint in case of I am wrong ?

  • 2
    $\begingroup$ Try proving that your idea works, and simultaneously try constructing a counterexample. That's exactly what we would do, but since it's your exercise, it makes more sense for you to do it. $\endgroup$ – Yuval Filmus Dec 1 '15 at 15:38
  • $\begingroup$ Thanks. I think that proof by contradiction is not difficult :) $\endgroup$ – user40545 Dec 1 '15 at 15:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.