def max_sub_deg_ordering(G):
    """returns ordering of nodes {v1,..., vn} where
    starting from v1, take v1 := max deg v in G
    v2 := max deg v in G - {v1}, 
    vj := min deg v in G - {v1, ..., vj-1}"""
    
    node_degrees = [[node, G.degree(node)] for node in G.nodes]
    ordering = []
    
    for _ in range(len(node_degrees)):
        # sorted from max to min degree
        node_degrees.sort(key=lambda x: x[1], reverse=True) 
        # take max degree node as vj
        node = node_degrees.pop(0)[0]                       
        ordering.append(node)                               
        for node_degree in node_degrees:       # update degrees per removing vj
            if G.has_edge(node, node_degree[0]):
                node_degree[1] -= 1
        
    return ordering