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

  • 9
    $\begingroup$ 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$. $\endgroup$
    – John D.
    Commented Jul 7, 2014 at 11:17
  • $\begingroup$ Sorry for not being completely clear in the question. Can these $\deg (v) -k$ edges be found in a polynomial time? $\endgroup$
    – simco
    Commented Jul 7, 2014 at 11:28
  • 7
    $\begingroup$ Just keep a single edge going from $v$ to each connected component... $\endgroup$
    – R B
    Commented Jul 7, 2014 at 11:37
  • 1
    $\begingroup$ 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). $\endgroup$
    – Stephan Krilow
    Commented Jul 7, 2014 at 13:33
  • 2
    $\begingroup$ @user17410 That should be an answer. $\endgroup$ Commented Jul 8, 2014 at 7:15

1 Answer 1


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))$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.