TADM2E 5.20

Traversing the graph G DFS O(n + m)
- If vertex M has degree >= k, add it to U
- - If vertex J (parent of M) was added to U, then add an edge MJ to R
- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U

Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.
If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.

--Bkarpov96 (talk) 08:53, 6 July 2020 (UTC)