trivially-perfect.py

# Trivially perfect graphs are the graphs that do not have a P4 path graph or a C4 cycle graph as induced subgraphs.
# Reference:  Brandstädt, Le & Spinrad (1999), theorem 6.6.1, p. 99; Golumbic (1978), theorem 2. Wolk (1962) and Wolk (1965) proved this for comparability graphs of rooted forests.

# Error: By mistake used DiGraphs here instead of undirected.

# returns true if C4 is present
def checkC4(graph):
    for vertex in graph:
        if(graph.degree(vertex) != 2):
            return False
    return True;

# returns true if P4 is present
def checkP4(graph):
    for vertex in graph:
        if(graph.degree(vertex) > 2):
            return False
    if(not graph.to_undirected().is_tree()):
        return False;
    return True;


def checkTP(graph):
    induced_subgraphs = list(graph.connected_subgraph_iterator(k=4, exactly_k=true))
    for G in induced_subgraphs:
        if(checkP4(G) or checkC4(G)):
            return False
    return True

# the input graph
G = DiGraph([(1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (4, 5), (4, 6), (5, 6), (5, 7), (5, 8), (6, 8), (6,7), (7,8)])

isTP = checkTP(G)
if(isTP):
    print("trivially perfect")
else:
    print("not trivially perfect")