# Preserving connectivity from a vertex by edges deletion

Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all the other vertices in $G$?

• If I'm not mistaken this is an easy task. Remove $v$ and count the connected components, let $k$ be that number. Then at most $\deg(v)-k$ edges can be removed from $v$. Commented Jul 7, 2014 at 11:17
• Sorry for not being completely clear in the question. Can these $\deg (v) -k$ edges be found in a polynomial time?
– simco
Commented Jul 7, 2014 at 11:28
• Just keep a single edge going from $v$ to each connected component...
– R B
Commented Jul 7, 2014 at 11:37
• I think you have been misled, this doesn't seem the right way to formulate the problem stated in the title; I would suggest looking at possible applications of the Gallai-Edmonds decomposition to your question (Thm 2.2.3 in Diestel's textbook).
– Stephan Krilow
Commented Jul 7, 2014 at 13:33
• @user17410 That should be an answer. Commented Jul 8, 2014 at 7:15

Construct a DFS traversal tree, starting from $v$.
The tree construction costs $O(|V|+|E|)$.
The identification of the edges that can be removed is $O(deg(v))$.