# TADM2E 5.20

From Algorithm Wiki

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)