<p>You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.</p>

<p>There is no $K_5$ minor, because the graph is planar. There is, however, a $K_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the <a href="https://en.wikipedia.org/wiki/Treewidth#Forbidden_minors" rel="noreferrer">forbidden minors for treewidth three</a>, the width is four.</p>

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

CC BY-SA 3.0
2016-09-06T22:33:52.607Z
Nice figure @David Eppstein. How did you draw it?
Chandra Chekuri
CC BY-SA 3.0
2016-09-06T22:47:12.953Z
Adobe Illustrator, mostly using their click, drag and snap copying operation to repeatedly triple a single equilateral triangle.
David Eppstein
CC BY-SA 3.0
2016-09-07T00:44:14.427Z
Thanks for the clear explanation! I should have realized that there can't be a $K_5$ since it is planar...
while False
CC BY-SA 3.0
2016-09-06T21:52:11.913Z
2016-09-06T22:05:10.640Z
2016-09-06T22:05:10.640Z
David Eppstein
<p><a href="http://mathworld.wolfram.com/SierpinskiSieveGraph.html" rel="nofollow noreferrer">Note <span class="math-container">$S_n$</span> the Sierpiński sieve graph of order <span class="math-container">$n$</span>, which is obtained from the connectivity of the Sierpiński sieve.</a></p>

<p><img src="https://i.sstatic.net/GfSwP.gif" alt="S_n"></p>

<p>For <span class="math-container">$n$</span> high enough, what is the treewidth of <span class="math-container">$S_n$</span>?</p>

<p>I think that I can show that it is at least <span class="math-container">$4$</span> (by obtaining <span class="math-container">$K_5$</span> as a graph minor), and that it is at most <span class="math-container">$5$</span> (by obtained a tree-decomposition scheme involving bags of size <span class="math-container">$6$</span>). My gut feeling is that it should be <span class="math-container">$5$</span>, but I cannot find a proper database for forbidden minors at treewidth <span class="math-container">$4$</span> (and I can't access Sanders' thesis mentioned <a href="https://cstheory.stackexchange.com/questions/9008/forbidden-minors-for-bounded-treewidth-graphs">here</a>).</p>

<treewidth>
Treewidth of deep Sierpiński Sieve Graph
while False
# Treewidth of deep Sierpiński Sieve Graph

(Asked by: username_0 on 2016-09-06)

[Note $S\_n$ the Sierpiński sieve graph of order $n$, which is obtained from the connectivity of the Sierpiński sieve.](http://mathworld.wolfram.com/SierpinskiSieveGraph.html)

![S_n](https://i.sstatic.net/GfSwP.gif)

For $n$ high enough, what is the treewidth of $S\_n$?

I think that I can show that it is at least $4$ (by obtaining $K\_5$ as a graph minor), and that it is at most $5$ (by obtained a tree-decomposition scheme involving bags of size $6$). My gut feeling is that it should be $5$, but I cannot find a proper database for forbidden minors at treewidth $4$ (and I can't access Sanders' thesis mentioned [here](https://cstheory.stackexchange.com/questions/9008/forbidden-minors-for-bounded-treewidth-graphs)).

**Tags:** treewidth


---

## 1 answers

### Answer by username_1 on 2016-09-06. Score: 17 | Accepted answer

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.

There is no $K\_5$ minor, because the graph is planar. There is, however, a $K\_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the [forbidden minors for treewidth three](https://en.wikipedia.org/wiki/Treewidth#Forbidden_minors), the width is four.

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

> **Comments:**
> **username_2**: Nice figure @username_1. How did you draw it?  
> **username_1**: Adobe Illustrator, mostly using their click, drag and snap copying operation to repeatedly triple a single equilateral triangle.  
> **username_0**: Thanks for the clear explanation! I should have realized that there can't be a $K_5$ since it is planar...  

---

