<p><a href="http://en.wikipedia.org/wiki/Turan%27s_theorem" rel="nofollow">Turan's theorem</a> exactly characterizes the densest graphs on n vertices with no k clique. <a href="http://en.wikipedia.org/wiki/Tur%C3%A1n_graph" rel="nofollow">The Turan graphs</a> are the maximal graphs, and they're very easy to construct. Is this what you want?</p>

CC BY-SA 2.5
2010-09-18T19:08:21.290Z
2010-09-18T19:08:21.290Z
Robin Kothari
<blockquote>
  <p>Given integers $k$ and $n$ with $2 \le k &lt; n$,
  how does one construct a graph on $n$ vertices
  that contains no $k$-clique and has the maximal
  number of edges? </p>
</blockquote>

<p>This sounds like basic combinatorics, but I don't know where to find the result.  Pointers would be welcome if this is well-known.</p>

<p>Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.</p>

<p>One graph with $n$ vertices that is guaranteed not to contain $K_k$ is $\overline{K_{n-k+2} + \overline{K_{k-2}}}$, the complement of the graph formed by the disjoint union of $K_{n-k+2}$ and $k-2$ isolated vertices.  Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique.  This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$.  However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.</p>

CC BY-SA 2.5
2010-09-18T21:10:13.580Z
I actually needed this to ask another question: http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique
András Salamon
<ds.algorithms><graph-theory><co.combinatorics>
How can one construct a densest graph with no k-clique?
András Salamon
# How can one construct a densest graph with no k-clique?

(Asked by: username_0 on 2010-09-18)

> Given integers $k$ and $n$ with $2 \le k < n$,
> how does one construct a graph on $n$ vertices
> that contains no $k$-clique and has the maximal
> number of edges?

This sounds like basic combinatorics, but I don't know where to find the result. Pointers would be welcome if this is well-known.

Ideally I would like a deterministic procedure to construct such a maximal graph in $n^{O(1)}$ time.

One graph with $n$ vertices that is guaranteed not to contain $K\_k$ is $\overline{K\_{n-k+2} + \overline{K\_{k-2}}}$, the complement of the graph formed by the disjoint union of $K\_{n-k+2}$ and $k-2$ isolated vertices. Whenever one picks $k$ vertices from it, at least two of these must be from the subset which is completely disconnected, so they cannot form a clique. This can clearly be constructed in polynomial time, and is quite dense for $k$ close to $n$. However, this construction yields rather sparse graphs when $k$ is small relative to $n$, so it seems unlikely to be the optimal construction.

**Tags:** ds.algorithms, graph-theory, co.combinatorics
> **Comments:**
> **username_0**: I actually needed this to ask another question: http://cstheory.stackexchange.com/questions/1441/hardness-of-parameterized-clique  

---

## 1 answers

### Answer by username_1 on 2010-09-18. Score: 7 | Accepted answer

[Turan's theorem](http://en.wikipedia.org/wiki/Turan%27s_theorem) exactly characterizes the densest graphs on n vertices with no k clique. [The Turan graphs](http://en.wikipedia.org/wiki/Tur%C3%A1n_graph) are the maximal graphs, and they're very easy to construct. Is this what you want?


---

