From the problem, it can be proven by induction that a pseudoforest is simply any graph formed by taking any subset of vertices and selecting a single edge connected to each one. Each edge must therefore be associated with one vertex: each use of the machine, you can take each vertex and associate any single attached edge with it, thus removing all associated edges. If only one edge is taken per vertex, it is guaranteed that only pseudoforests will be formed, and also that all valid pseudoforests will be considered. Each vertex can only claim one edge per machine use, which means that the vertex with the most claimed edges determines the number of times the machine must be used. Therefore, the solution to this problem involves taking each edge and assigning it to one of its two vertices such that the most edges attached to a single vertex is minimized.

You can attempt a greedy algorithm, where each edge is placed at the vertex with fewer currently claimed edges, but this fails to yield the correct results for moderately complex graphs. You can augment this greedy algorithm by taking into consideration all past assignments, and undoing them if necessary. By this, we mean that the idea of flows and augmenting paths will be used to solve this problem.

Think of the graph as initially completely disjoint, with no edges. Iterate through all the edges, and for each edge ~(a,b)~, find the minimum out of all vertices reachable by augmenting paths previously constructed, and find a path to that vertex. If the path found starts at ~a~, draw an arrow pointing from ~a~ to ~b~. If it starts at ~b~, draw one instead from ~b~ to ~a~. These arrows are augmenting paths. Now, take all the arrows which comprise the augmenting path previously found, and reverse every one of them. Finally, add one to the vertex which the arrows originally pointed to. You can think of vertices as "sinks" in a flow network.

Once that procedure has been completed for every edge, it is guaranteed that all the edges will have been assigned optimally so that the most edges associated with a single vertex is minimized. The answer is the maximum out of all values stored by the vertices.

Time complexity: ~\mathcal O(NM)~

The proof of why this always leads to an optimal answer can be found by exploring a more complicated solution.

• Transform every edge ~(a,b)~ into a vertex adjacent to ~a~ and ~b~, and form a bipartite graph between former edges and the original vertices.
• Use a maximum flow/bipartite matching algorithm in a binary searching pattern to find the lowest ~k~ such that, when the edges are connected to the source and original vertices to the sink, each vertex has a flow capacity to the sink of ~k~ and it is possible for the sink to achieve a flow value of ~M~.

This solution readily reduces into the one previously described as the source nodes can be augmented in any order, meaning that it is unnecessary to empty the network when checking different ~k~ values. Therefore, just augment the lowest node possible with each source node and disregard the super sink, treating each vertex as a sink itself. This is allowed because if an edge augments a higher node value than another, it cannot possibly affect which node that other edge augments.

In the end, it becomes the greedy algorithm described earlier, and the final challenge of proving that converting edges to vertices is unnecessary is left up to the reader.