def make_k_sparse_compl_func(k):
    """Return func f(g,s) -> True if s is k-sparse in complement of g.

    Given nonnegative integer k, returns a function f taking a graph g
    and a subset of the vertex set of g, and returning bool. The
    returned function returns True if s is k-sparse in the complement
    of g.

    The returned function is an induced-hereditary predicate, as the
    term is used in genramsey.py.

    Arguments:
    k -- nonnegative int; the "k" in k-sparse

    See isograph.py for our graph representation.

    >>> f0 = make_k_sparse_compl_func(0)
    >>> f1 = make_k_sparse_compl_func(1)
    >>> f2 = make_k_sparse_compl_func(2)
    >>> g = [ [2,3,4], [3,4], [0,4], [0,1], [0,1,2] ]
    >>> s = [0,1,2,3,4]
    >>> f0(g, s)
    False
    >>> f1(g, s)
    False
    >>> f2(g, s)
    True
    >>> s = [0,1,3,4]
    >>> f0(g, s)
    False
    >>> f1(g, s)
    True
    >>> f2(g, s)
    True
    >>> s = [0,2,4]
    >>> f0(g, s)
    True
    >>> f1(g, s)
    True
    >>> f2(g, s)
    True

    """
    def is_k_sparse_compl(g, s):
        for v in s:
            d = 0
            for x in s:
                if x != v and x not in g[v]:
                    d += 1
                    if d > k:
                        return False
        return True

    return is_k_sparse_compl