# 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$?

## migrated from cstheory.stackexchange.comJul 9 '14 at 17:16

This question came from our site for theoretical computer scientists and researchers in related fields.

• 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$. – John D. Jul 7 '14 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 Jul 7 '14 at 11:28
• Just keep a single edge going from $v$ to each connected component... – R B Jul 7 '14 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 Jul 7 '14 at 13:33
• @user17410 That should be an answer. – David Richerby Jul 8 '14 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))$.