def _maximal_independent_set(G):
 result = set()
 remaining = set(G)
 while remaining:
  G = G.subgraph(remaining)
  v = min(remaining, key=G.degree)
  result.add(v)
  remaining -= (set(G[v]) | {v})
 return result

def _maximal_independent_set ( G ) : result = set ( ) remaining = set ( G ) while remaining : G = G . subgraph ( remaining ) v = min ( remaining , key = G . degree ) result . add ( v ) remaining -= ( set ( G [ v ] ) | { v } ) return result
returns a maximal independent set of nodes in g by repeatedly choosing an independent node of minimum degree .