<p>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.</p>

<p><a href="https://i.sstatic.net/3SH9C.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3SH9C.png" alt="enter image description here"></a></p>

<p>In this example, some other valid removal orderings could still produce a maximal clique. Probably there are more elaborate versions of this example that force the remaining clique to be non-maximal for all valid removal orderings.</p>

CC BY-SA 3.0
2018-01-03T08:35:37.597Z
Thank you, David, I have read your two papers about MCE and I don't know that you were here. This counterexample is enough to my question. Thank you again.
Yinuo
CC BY-SA 3.0
2018-01-06T07:07:31.787Z
How about adding a vertex to each edge of the Peterson graph.  The new vertex is adjacent to both ends of the edge, and hence has degree two. The decomposition will remove all new vertices first, and then it ends with an edge.
Yixin Cao
CC BY-SA 3.0
2018-01-06T08:08:07.797Z
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.
David Eppstein
CC BY-SA 3.0
2018-01-03T07:55:49.477Z
2018-01-03T07:55:49.477Z
David Eppstein
<p>I have read <a href="https://arxiv.org/pdf/1006.5440.pdf" rel="nofollow noreferrer">David Eppstein's paper</a> about <a href="https://en.wikipedia.org/wiki/Clique_problem#Listing_all_maximal_cliques" rel="nofollow noreferrer">maximal clique enumeration</a> by using degeneracy order. It has mentioned the core decomposition, which is removing the vertex with the smallest degree iteratively. </p>

<p>And I pick up with a theorem:<br>
If we remove the vertex with the smallest degree iteratively until the smallest degree is |<em>S</em>|-1, where <em>S</em> is the remaining graph, is <em>S</em> a maximal clique?</p>

<p>example graph:</p>

<p><img src="https://i.sstatic.net/HOF1K.png" alt="example graph"></p>

<p>In this graph, we will delete vertex <em>a</em> whose degree is the smallest one ( deg(<em>a</em>)=2 ), and then delete vertex <em>f</em>. And we will get the 4-maximal clique {<em>b,c,d,e</em>}.</p>

<p>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?</p>

<p><strong>PS:</strong> </p>

<p>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.</p>

<p>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.</p>

<p>Also notice that when the vertex v is removed from the graph, all it's neighbors' degree will decrease one.</p>

<graph-theory><clique>
Will core decomposition get a maximal clique?
Yinuo
# Will core decomposition get a maximal clique?

(Asked by: username_0 on 2018-01-03)

I have read [David Eppstein's paper](https://arxiv.org/pdf/1006.5440.pdf) about [maximal clique enumeration](https://en.wikipedia.org/wiki/Clique_problem#Listing_all_maximal_cliques) 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:

![example graph](https://i.sstatic.net/HOF1K.png)

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.

**Tags:** graph-theory, clique

---

## 1 answers

### Answer by username_1 on 2018-01-03. Score: 3 | Accepted answer

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.

[![enter image description here](https://i.sstatic.net/3SH9C.png)](https://i.sstatic.net/3SH9C.png)

In this example, some other valid removal orderings could still produce a maximal clique. Probably there are more elaborate versions of this example that force the remaining clique to be non-maximal for all valid removal orderings.

> **Comments:**
> **username_0**: Thank you, David, I have read your two papers about MCE and I don't know that you were here. This counterexample is enough to my question. Thank you again.  
> **username_2**: How about adding a vertex to each edge of the Peterson graph.  The new vertex is adjacent to both ends of the edge, and hence has degree two. The decomposition will remove all new vertices first, and then it ends with an edge.  
> **username_1**: 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.  

---

