Hi, can you give me a hint about this problem ??

Given a connected simple graph with n vertices and m edges, find the minimum number of operations required to remove the graph completely

in an operation you can do one of the following things:

1- remove a vertex from the graph

2- remove 2 vertices connecting to an edge

Auto comment: topic has been updated by SheikhSoheil (previous revision, new revision, compare).Auto comment: topic has been updated by SheikhSoheil (previous revision, new revision, compare).It is always optimal to perform operations of type $$$2$$$ as many times as possible. So the answer to the problem is $$$= n - $$$ maximum matching.

For a general graph, you can solve it in $$$O(n^3)$$$ and in case of a bipartite graph, you can do the same in $$$O(n \sqrt{n})$$$.