<p>I think if the size of clique, i.e. $p$ is prime, then the following statement is true.</p>

<p>If a complete graph of $n$ vertices can be decomposed into cliques of size p with $p≤n$ then $n-1$ or $n-p$ is divided by $p(p-1)$.</p>

<p>The above statement also holds if $p=2^k$.</p>

CC BY-SA 3.0
2014-09-08T05:05:25.050Z
2014-09-08T06:13:50.877Z
2014-09-08T06:13:50.877Z
Dibyayan
<p>If you want to decompose a complete graph into triangles then look for &quot;steiner triple system&quot; (STS). You will find some there: <a href="http://web.archive.org/web/20210624054646/https://www.steinertriples.fr/" rel="nofollow noreferrer">http://web.archive.org/web/20210624054646/https://www.steinertriples.fr/</a></p>
<p>If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are &quot;Balanced Incomplete Block Designs&quot;. If you want to know more about that, try to find the book from Douglas Stinson named &quot;Combinatorial designs: construction and analysis&quot;.</p>
<p>Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a <code>(v,k,1)</code>-BIBD whenever one exists for <code>k&lt;=5</code>, and as for larger values of <code>k</code>, well, it depends.</p>
<p>Either way, if you find a combinatorial design that it cannot build come tell us about it ! <code>:-P</code></p>
<p>Nathann</p>

CC BY-SA 3.0
2014-09-08T05:24:12.723Z
The reference to the book indeed helped.
Dibyayan
CC BY-SA 4.0
2014-09-07T08:43:10.703Z
2023-03-24T19:04:48.620Z
2023-03-24T19:04:48.620Z
Nathann Cohen
<p>The following exercise problem is from the book of D.B.West which i could solve:</p>
<blockquote>
<p>If a complete graph can be decomposed into triangles then <span class="math-container">$n-1$</span> or <span class="math-container">$n-3$</span> is divisible by 6.</p>
</blockquote>
<p>So my questions are the following,</p>
<blockquote>
<ol>
<li><p>If a complete graph of <span class="math-container">$n$</span> vertices can be decomposed into cliques of size <span class="math-container">$p$</span> with <span class="math-container">$p\leq n$</span> then what should be the relation between <span class="math-container">$n$</span> and <span class="math-container">$p$</span>.</p>
</li>
<li><p>What is the official name of this problem in the literature ?</p>
</li>
</ol>
</blockquote>
<p>Any links/hints would be helpful.</p>

<graph-theory>
Decompose a complete graph into smaller cliques
Dibyayan
# Decompose a complete graph into smaller cliques

(Asked by: username_0 on 2014-09-07)

The following exercise problem is from the book of D.B.West which i could solve:

> If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.

So my questions are the following,

> 1. If a complete graph of $n$ vertices can be decomposed into cliques of size $p$ with $p\leq n$ then what should be the relation between $n$ and $p$.
> 2. What is the official name of this problem in the literature ?

Any links/hints would be helpful.

**Tags:** graph-theory

---

## 2 answers

### Answer by username_1 on 2014-09-07. Score: 12 | Accepted answer

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: <http://web.archive.org/web/20210624054646/https://www.steinertriples.fr/>

If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are "Balanced Incomplete Block Designs". If you want to know more about that, try to find the book from Douglas Stinson named "Combinatorial designs: construction and analysis".

Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a `(v,k,1)`-BIBD whenever one exists for `k<=5`, and as for larger values of `k`, well, it depends.

Either way, if you find a combinatorial design that it cannot build come tell us about it ! `:-P`

Nathann

> **Comments:**
> **username_0**: The reference to the book indeed helped.  

---

### Answer by username_0 on 2014-09-08. Score: 0

I think if the size of clique, i.e. $p$ is prime, then the following statement is true.

If a complete graph of $n$ vertices can be decomposed into cliques of size p with $p≤n$ then $n-1$ or $n-p$ is divided by $p(p-1)$.

The above statement also holds if $p=2^k$.


---

