from sage.graphs.independent_sets import IndependentSets
from math import factorial

def choose2(n):
    return ((n * (n - 1)) / 2)
    
def root_in_poly(poly, root):
    root_list = poly.roots()
    for tuple in root_list:
        for elt in tuple:
            if root == elt:
                return True
    return False
    
def build_ip(graph):
    number_of = [0] * graph.order()
    for set in IndependentSets(graph):
        number_of[len(set)] += 1
    poly = 0
    for index in range(0, len(number_of)):
        poly += (number_of[index]) * (x ** index)
    return poly
    
def main():
    R.<x> = QQ[]
    root = -1
    for v in range(4, 10):
        count = 0
        for g in graphs(v):
            if g.is_connected():
                ip = build_ip(g)
                if root_in_poly(ip, root):
                    count += 1
        print(v, ": ", count)
        
main()