<p>The smallest such example that is known to the <a href="https://houseofgraphs.org/" rel="noreferrer">House of Graphs</a> is for <span class="math-container">$k = 9$</span>. There is a graph of tree-width <span class="math-container">$9$</span> having only <span class="math-container">$44$</span> edges (while the <span class="math-container">$10$</span>-clique contains <span class="math-container">$45$</span> edges).</p>

CC BY-SA 4.0
2024-05-26T12:49:09.167Z
Interesting, thanks! I'd be curious to know if this is "minimal" -- what about the smallest number of edges required for treewidth 6, 7, 8.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-05-24T12:53:07.300Z
2024-05-24T12:53:07.300Z
tomil
<p><a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">Treewidth</a> is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth <span class="math-container">$k$</span>.</p>
<p>A natural family of graphs to consider are the <a href="https://en.wikipedia.org/wiki/Clique_(graph_theory)" rel="noreferrer">cliques</a>: a clique on <span class="math-container">$k+1$</span> vertices has treewidth <span class="math-container">$k$</span>, and has <span class="math-container">$k (k+1) / 2$</span> edges. However, asymptotically, there are graphs of treewidth <span class="math-container">$k$</span> whose number of edges is linear rather than quadratic, e.g., cubic expanders as mentioned in <a href="https://cstheory.stackexchange.com/questions/39071/maximum-treewidth-of-a-graphs-with-m-edges">this question</a>. So cliques are not optimal. My question is: <strong>what is the smallest example of a graph of treewidth <span class="math-container">$k$</span> having less edges than the <span class="math-container">$(k+1)$</span>-clique?</strong></p>
<p>I have checked experimentally that all graphs of 14 edges or less have treewidth at most 4, so they do not beat the 6-clique which has 15 edges and treewidth 5. Hence, the smallest treewidth for which I do not know the answer is 6. Specifically: the 7-clique has 21 edges and treewidth 6, but <strong>is there a graph of treewidth 6 having 20 edges or less?</strong></p>
<p>(Note that we could ask the same question of the minimal number of <em>vertices</em> required for a graph to have treewidth <span class="math-container">$k$</span>, but then it is uninteresting: you need <span class="math-container">$k+1$</span> vertices for a graph to have treewidth <span class="math-container">$k$</span>, and this is achieved by the <span class="math-container">$(k+1)$</span>-clique.)</p>

CC BY-SA 4.0
2024-01-24T12:36:39.170Z
Related: having treewidth of $O(n)$ where $n$ is the number of vertices is known to be equivalent to having large expansion and bounded degree, see [1, Theorem 8]. The probabilistic construction of expanders would give you a graph with treewidth $k$ with $O(k)$ vertices whp. [1] Böttcher, Julia, et al. "Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs." European Journal of Combinatorics 31.5 (2010)
holf
CC BY-SA 4.0
2024-01-24T23:09:41.680Z
Re the previous comment. The quantifiers are not quite correct I believe. $\Omega(1)$ vertex expansion suffices for $\Omega(n)$ treewidth. And there exist bounded degree graphs (in particular degree 3) with $\Omega(1)$ vertex expansion. Edge and vertex expansion are related by the maximum degree, and hence one obtains vertex expansion automatically from edge expansion if degree is fixed (such as 3).
Chandra Chekuri
<graph-theory><treewidth><extremal-combinatorics>
What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?
Antoine Amarilli 'a3nm'
# What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?

(Asked by: username_0 on 2024-01-24)

[Treewidth](https://en.wikipedia.org/wiki/Treewidth) is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$.

A natural family of graphs to consider are the [cliques](https://en.wikipedia.org/wiki/Clique_(graph_theory)): a clique on $k+1$ vertices has treewidth $k$, and has $k (k+1) / 2$ edges. However, asymptotically, there are graphs of treewidth $k$ whose number of edges is linear rather than quadratic, e.g., cubic expanders as mentioned in [this question](https://cstheory.stackexchange.com/questions/39071/maximum-treewidth-of-a-graphs-with-m-edges). So cliques are not optimal. My question is: **what is the smallest example of a graph of treewidth $k$ having less edges than the $(k+1)$-clique?**

I have checked experimentally that all graphs of 14 edges or less have treewidth at most 4, so they do not beat the 6-clique which has 15 edges and treewidth 5. Hence, the smallest treewidth for which I do not know the answer is 6. Specifically: the 7-clique has 21 edges and treewidth 6, but **is there a graph of treewidth 6 having 20 edges or less?**

(Note that we could ask the same question of the minimal number of *vertices* required for a graph to have treewidth $k$, but then it is uninteresting: you need $k+1$ vertices for a graph to have treewidth $k$, and this is achieved by the $(k+1)$-clique.)

**Tags:** graph-theory, treewidth, extremal-combinatorics
> **Comments:**
> **username_1**: Related: having treewidth of $O(n)$ where $n$ is the number of vertices is known to be equivalent to having large expansion and bounded degree, see [1, Theorem 8]. The probabilistic construction of expanders would give you a graph with treewidth $k$ with $O(k)$ vertices whp. [1] Böttcher, Julia, et al. "Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs." European Journal of Combinatorics 31.5 (2010)  
> **username_2**: Re the previous comment. The quantifiers are not quite correct I believe. $\Omega(1)$ vertex expansion suffices for $\Omega(n)$ treewidth. And there exist bounded degree graphs (in particular degree 3) with $\Omega(1)$ vertex expansion. Edge and vertex expansion are related by the maximum degree, and hence one obtains vertex expansion automatically from edge expansion if degree is fixed (such as 3).  

---

## 1 answers

### Answer by username_3 on 2024-05-24. Score: 7

The smallest such example that is known to the [House of Graphs](https://houseofgraphs.org/) is for $k = 9$. There is a graph of tree-width $9$ having only $44$ edges (while the $10$-clique contains $45$ edges).

> **Comments:**
> **username_0**: Interesting, thanks! I'd be curious to know if this is "minimal" -- what about the smallest number of edges required for treewidth 6, 7, 8.  

---

