<p>You can also look for Moon-Moser theorem in <a href="http://books.google.com/books?id=LXDe1XHJCYIC&amp;pg=PA170&amp;lpg=PA170&amp;dq=fomin%20kratsch&amp;source=bl&amp;ots=jb3ERCRty5&amp;sig=lX-3W7vuLfwyROzIJavklk_pXvc&amp;hl=en&amp;ei=87qCToW8CrTUiALF4uynBg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CBwQ6AEwAA#v=onepage&amp;q=moon%20moser&amp;f=false" rel="noreferrer">Fomin-Kratsch Exact Algorithms book</a></p>

CC BY-SA 3.0
2011-09-28T06:09:15.387Z
2011-09-28T06:14:40.713Z
2011-09-28T06:14:40.713Z
vortk
<p>Here is a copy of the 1965 paper by Moon and Moser: <a href="http://users.monash.edu.au/~davidwo/MoonMoser65.pdf" rel="noreferrer">http://users.monash.edu.au/~davidwo/MoonMoser65.pdf</a></p>

<p>Note that the result was actually first proved in 1960 by Miller and Muller:
<a href="http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf" rel="noreferrer">http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf</a></p>

CC BY-SA 3.0
2014-07-16T06:16:02.573Z
2014-07-16T06:16:02.573Z
user26635
<p>The answers that have been given so far are great. I thought I'd add some references.</p>

<ul>
<li>The Moon-Moser theorem was independently proved by Miller and Muller [1960] in a technical report.</li>
<li>Wood [2011] and Vatter [2011] give simpler proofs of the Theorem, using basically the approach outlined by David.</li>
</ul>

<p>Miller, R. E. and Muller, D. E. 1960. A problem of maximum consistent subsets. IBM
Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, NY.</p>

<p>Vatter, V. 2011. <a href="http://www.math.ufl.edu/~vatter/publications/sss-mis/sss-mis.pdf" rel="nofollow">Maximal independent sets and separating covers</a>. American Mathematical
Monthly 118, 418-423.</p>

<p>Wood, D. R. 2011. <a href="http://arxiv.org/abs/1104.1243" rel="nofollow">On the number of maximal independent sets in a graph</a>. CoRR abs/1104.1243.</p>

CC BY-SA 3.0
2017-07-25T16:04:24.480Z
Möller asked for Moon and Moser, you answered Miller and Muller, and a piece from Mathematical Monthly.  What's going on?
John K.
CC BY-SA 3.0
2011-09-29T12:03:37.340Z
2011-09-29T15:31:33.250Z
2011-09-29T15:31:33.250Z
Serge Gaspers
<p>I don't have a copy of Moon &amp; Moser at hand, but: the maximum number of distinct maximal cliques in an $n$-node graph (with $n>1$) is $3^{n/3}$, $4\cdot 3^{(n-4)/3}$, or $2\cdot 3^{(n-2)/3}$, according to the value of $n$ mod 3. I think it's a little easier to see this in the complementary form of counting maximal independent sets.</p>

<p>The lower bound is what you're really asking for, and is mostly given already in the comments above: form a graph from the disjoint union of copies of $K_2$ and $K_3$, using as many copies of $K_3$ as possible. Each maximal independent set has exactly one node from each of these complete subgraphs from which the formula follows.</p>

<p>I seem to recall that the upper bound proof of Moon and Moser involved transforming a graph into the lower bound form (or the complementary form for maximal cliques), at each step not decreasing the number of independent sets or cliques. But there's a different way of proving it that leads to worst-case-optimal backtracking algorithms for listing all the cliques or independent sets (see e.g. my paper <a href="http://arxiv.org/abs/cs.DS/0011009">arXiv:cs/0011009</a>), which I'll only sketch here because the details are a bit tedious. If there's a vertex $v$ of degree three or more in the given graph $G$, then each maximal independent set of $G$ is either a maximal independent set in $G\setminus v$ or it includes $v$ and is a maximal independent set of the graph formed from $G$ by removing $v$ and all of its neighbors. By induction (plugging in the formula for the number of independent sets in these two smaller graphs, with some case analysis mod 3) the bound follows. On the other hand, if no high degree vertex exists then the graph is a disjoint union of paths and cycles, in which one can calculate the number of independent sets directly.</p>

CC BY-SA 3.0
2011-09-28T05:27:50.633Z
Thank you very much for taking the time to write out a very detailed answer.
Josephine Moeller
CC BY-SA 3.0
2014-03-03T09:24:08.890Z
@David Eppstein do you have a similar result for the bound on the number of maximal k-plexs (where k-plex is similar to a clique except from the fact the any node can be disconnected from at most k other nodes)
user844541
CC BY-SA 3.0
2011-09-28T04:24:45.433Z
2011-09-28T04:24:45.433Z
David Eppstein
<p>I'm looking for the full text of the Moon and Moser 1965 clique result <em>On Cliques in Graphs</em> (there exist graphs with a number of maximal cliques exponential in <span class="math-container">$n$</span>). My university's paywall doesn't have access to the particular journal. (In fact, the <a href="https://doi.org/10.1007/BF02760024" rel="nofollow noreferrer">preview</a> provides the first few sentences of the proof, but then leaves me without the rest!)</p>
<p>I was interested in this result related to a research direction I was pursuing, but the direction has changed slightly, so admittedly my interest is now purely academic curiosity.</p>
<p>My question is:</p>
<blockquote>
<p>Is there a link to the full text of the paper somewhere OR another paper that sketches the proof OR if a proof sketch is short enough to reproduce here, does anyone know it? Also, I'm interested in the class of graphs with an exponential number of cliques.</p>
</blockquote>
<p>I added the BibTeX for reference:</p>
<pre><code>@article {springerlink:10.1007/BF02760024,
   author = {Moon, J. and Moser, L.},
   affiliation = {University of Alberta Edmonton Canada},
   title = {On cliques in graphs},
   journal = {Israel Journal of Mathematics},
   publisher = {Hebrew University Magnes Press},
   issn = {0021-2172},
   keyword = {Computer Science},
   pages = {23-28},
   volume = {3},
   issue = {1},
   url = {http://dx.doi.org/10.1007/BF02760024},
   note = {10.1007/BF02760024},
   year = {1965}
}
</code></pre>

CC BY-SA 3.0
2011-09-27T22:50:54.963Z
you can get a second page here: http://www.mendeley.com/research/on-cliques-in-graphs/# :)
Suresh Venkat
CC BY-SA 3.0
2011-09-27T23:06:14.830Z
Argh! Curse you!
Josephine Moeller
CC BY-SA 3.0
2011-09-27T23:06:20.717Z
Take the complete graph on $2n$ nodes and remove a perfect matching; there are $2^n$ maximal cliques.
Jukka Suomela
CC BY-SA 3.0
2011-09-27T23:11:32.213Z
@Jukka: Ah, I was wondering about doing something like that. Thanks.
Josephine Moeller
CC BY-SA 3.0
2011-09-27T23:34:23.427Z
The actual tight lower bound is by removing a set of disjoint triangles instead of a perfect matching. It gives $3^{n/3}$ cliques rather than $2^{n/2}$, slightly more.
David Eppstein
CC BY-SA 3.0
2011-09-28T01:01:50.413Z
Ah, so the bound comes from the fact that $x^x$ maxes out at $3^{1/3}$ for integer $x > 2$.
Josephine Moeller
CC BY-SA 3.0
2011-09-28T03:38:16.850Z
answers please, not comments.
Suresh Venkat
<reference-request><graph-theory><co.combinatorics><clique>
The number of cliques in a graph: the Moon and Moser 1965 result
Josephine Moeller
# The number of cliques in a graph: the Moon and Moser 1965 result

(Asked by: username_0 on 2011-09-27)

I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't have access to the particular journal. (In fact, the preview provides the first few sentences of the proof, but then leaves me without the rest!)
I was interested in this result related to a research direction I was pursuing, but the direction has changed slightly, so admittedly my interest is now purely academic curiosity.
My question is:

Is there a link to the full text of the paper somewhere OR another paper that sketches the proof OR if a proof sketch is short enough to reproduce here, does anyone know it? Also, I'm interested in the class of graphs with an exponential number of cliques.

I added the BibTeX for reference:
@article {springerlink:10.1007/BF02760024,
   author = {Moon, J. and Moser, L.},
   affiliation = {University of Alberta Edmonton Canada},
   title = {On cliques in graphs},
   journal = {Israel Journal of Mathematics},
   publisher = {Hebrew University Magnes Press},
   issn = {0021-2172},
   keyword = {Computer Science},
   pages = {23-28},
   volume = {3},
   issue = {1},
   url = {http://dx.doi.org/10.1007/BF02760024},
   note = {10.1007/BF02760024},
   year = {1965}
}

**Tags:** reference-request, graph-theory, co.combinatorics, clique

> **Comments:**
> **username_1**: you can get a second page here: http://www.mendeley.com/research/on-cliques-in-graphs/# :)  
> **username_0**: Argh! Curse you!  
> **username_2**: Take the complete graph on $2n$ nodes and remove a perfect matching; there are $2^n$ maximal cliques.  
> **username_0**: @Jukka: Ah, I was wondering about doing something like that. Thanks.  
> **username_3**: The actual tight lower bound is by removing a set of disjoint triangles instead of a perfect matching. It gives $3^{n/3}$ cliques rather than $2^{n/2}$, slightly more.  
> **username_0**: Ah, so the bound comes from the fact that $x^x$ maxes out at $3^{1/3}$ for integer $x > 2$.  
> **username_1**: answers please, not comments.  

---

## 4 answers

### Answer by username_3 on 2011-09-28. Score: 20 | Accepted answer

I don't have a copy of Moon & Moser at hand, but: the maximum number of distinct maximal cliques in an $n$-node graph (with $n>1$) is $3^{n/3}$, $4\cdot 3^{(n-4)/3}$, or $2\cdot 3^{(n-2)/3}$, according to the value of $n$ mod 3. I think it's a little easier to see this in the complementary form of counting maximal independent sets.

The lower bound is what you're really asking for, and is mostly given already in the comments above: form a graph from the disjoint union of copies of $K\_2$ and $K\_3$, using as many copies of $K\_3$ as possible. Each maximal independent set has exactly one node from each of these complete subgraphs from which the formula follows.

I seem to recall that the upper bound proof of Moon and Moser involved transforming a graph into the lower bound form (or the complementary form for maximal cliques), at each step not decreasing the number of independent sets or cliques. But there's a different way of proving it that leads to worst-case-optimal backtracking algorithms for listing all the cliques or independent sets (see e.g. my paper [arXiv:cs/0011009](http://arxiv.org/abs/cs.DS/0011009)), which I'll only sketch here because the details are a bit tedious. If there's a vertex $v$ of degree three or more in the given graph $G$, then each maximal independent set of $G$ is either a maximal independent set in $G\setminus v$ or it includes $v$ and is a maximal independent set of the graph formed from $G$ by removing $v$ and all of its neighbors. By induction (plugging in the formula for the number of independent sets in these two smaller graphs, with some case analysis mod 3) the bound follows. On the other hand, if no high degree vertex exists then the graph is a disjoint union of paths and cycles, in which one can calculate the number of independent sets directly.

> **Comments:**
> **username_0**: Thank you very much for taking the time to write out a very detailed answer.  
> **username_8**: @username_3 do you have a similar result for the bound on the number of maximal k-plexs (where k-plex is similar to a clique except from the fact the any node can be disconnected from at most k other nodes)  

---

### Answer by username_4 on 2011-09-28. Score: 7

You can also look for Moon-Moser theorem in [Fomin-Kratsch Exact Algorithms book](http://books.google.com/books?id=LXDe1XHJCYIC&pg=PA170&lpg=PA170&dq=fomin%20kratsch&source=bl&ots=jb3ERCRty5&sig=lX-3W7vuLfwyROzIJavklk_pXvc&hl=en&ei=87qCToW8CrTUiALF4uynBg&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBwQ6AEwAA#v=onepage&q=moon%20moser&f=false)


---

### Answer by username_5 on 2014-07-16. Score: 7

Here is a copy of the 1965 paper by Moon and Moser: <http://users.monash.edu.au/~davidwo/MoonMoser65.pdf>

Note that the result was actually first proved in 1960 by Miller and Muller:
<http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf>


---

### Answer by username_6 on 2011-09-29. Score: 6

The answers that have been given so far are great. I thought I'd add some references.

* The Moon-Moser theorem was independently proved by Miller and Muller [1960] in a technical report.
* Wood [2011] and Vatter [2011] give simpler proofs of the Theorem, using basically the approach outlined by David.

Miller, R. E. and Muller, D. E. 1960. A problem of maximum consistent subsets. IBM
Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, NY.

Vatter, V. 2011. [Maximal independent sets and separating covers](http://www.math.ufl.edu/~vatter/publications/sss-mis/sss-mis.pdf). American Mathematical
Monthly 118, 418-423.

Wood, D. R. 2011. [On the number of maximal independent sets in a graph](http://arxiv.org/abs/1104.1243). CoRR abs/1104.1243.

> **Comments:**
> **username_7**: Möller asked for Moon and Moser, you answered Miller and Muller, and a piece from Mathematical Monthly.  What's going on?  

---

