I have read David Eppstein's paper about maximal clique enumeration by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree iteratively.
And I pick up with a theorem:
If we remove the vertex with the smallest degree iteratively until the smallest degree is |S|-1, where S is the remaining graph, is S a maximal clique?
example graph:
In this graph, we will delete vertex a whose degree is the smallest one ( deg(a)=2 ), and then delete vertex f. And we will get the 4-maximal clique {b,c,d,e}.
I cannot prove this theorem but I also can't find a counterexample. Is there anyone can help me figure out this theorem right or wrong?
PS:
Clique is a subgraph whose every vertex is adjacent to each other. And maximal clique is a clique that cannot be contained by another clique, it means the maximal one cannot be extended.
I can prove the remaining graph that above algorithm produced is not a maximum clique which is the largest one in the graph, but I can't prove this graph whether is a maximal clique.
Also notice that when the vertex v is removed from the graph, all it's neighbors' degree will decrease one.