def select_first_node(g):

    """
    :param g: the graph
    :return: the first node of the node sequence based on which the graph will be partitioned. We select the first node
    as the node which has the lowest degree
    """
    all_degrees = []
    node_list = list(range(0, len(g)))
    for node in node_list:
        all_degrees.append(g.degree[node])
    return all_degrees.index(min(all_degrees))