# Will core decomposition get a maximal clique?

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.

No. The illustration shows a graph (the graph of a cube with one corner truncated) and a valid removal sequence such that the vertices left at the point when the minimum degree equals $|S|-1$ (the two red vertices) do not form a maximal clique.
• You mean, keeping the existing edge but adding a new degree-two vertex adjacent to its endpoints? That should work with any triangle-free cubic graph (e.g. $K_{3,3}$); using Petersen is overkill. Jan 6, 2018 at 8:08