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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.