# two connected graph - find linear spanning subgrap such that subgraph is still connected

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 ?

• 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. – Yuval Filmus Dec 1 '15 at 15:38
• Thanks. I think that proof by contradiction is not difficult :) – user40545 Dec 1 '15 at 15:46