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$?
Construct a DFS traversal tree, starting from $v$.

You can remove all edges of v that are not part of the tree.

The tree construction costs $O(|V|+|E|)$.

The identification of the edges that can be removed is $O(deg(v))$.