<p>As David pointed out, you basically ask for bounds on the treewidth of a connected graph with average degree 3. For the more special case of 3-regular graphs, the following lower and upper bounds can be obtained. Denoting by pw(G) the pathwidth of a graph G, it is clear that</p>

<p>(1) tw(G) &lt;= pw(G) for any graph G (as a path decomposition is a tree decomposition)</p>

<p>It is proved in [1] that</p>

<p>(2) For every \epsilon > 0, there exists an integer n_0 such that for any 3-regular graph G on n >= n_0 vertices, pw(G) &lt;= n/6 + \epsilon*n.</p>

<p>This gives you an upper bound of roughly n/6 on the treewidth of 3-regular graphs.</p>

<p>For an almost sure lower bound, I cite from [2]:</p>

<p>"As random cubic graphs almost surely have bisection width at least 0.101 n (Kostochka, Melnikov, 1992), they have almost surely no separator of size smaller than n/20"
and thus almost surely no tree decomposition of width smaller than n/20.</p>

<p>For a "sure" lower bound on the bisection width, [3] showed an infinite family of 3-regular graphs, such that each graph G=(V,E) in this family has bisection width at least 0.082 * |V|.</p>

<p>[1] Fedor V. Fomin, Kjartan Høie: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5): 191-196 (2006)</p>

<p>[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb. 29(3): 777-791 (2008)</p>

<p>[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: New spectral lower bounds on the bisection width of graphs. Theor. Comput. Sci. 320(2-3): 155-174 (2004)</p>

CC BY-SA 2.5
2010-08-17T03:17:16.837Z
Thank you, Serge. The bound via pathwidth is probably more accessible to me at this stage than the one via expander graphs; I haven't read either proof yet, though.
gphilip
CC BY-SA 2.5
2010-08-17T02:36:00.507Z
2010-08-17T02:36:00.507Z
Serge Gaspers
<p>Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but Θ(n) is best possible, yes.</p>

CC BY-SA 2.5
2010-08-17T01:33:09.067Z
Thanks, that answers my question.

To elaborate David's answer a bit, let H be a connected 3-regular graph on 2n vertices. H then has 3n edges. Let G be a tree on 2n vertices obtained by removing n+1 edges from H. Adding n of these edges back to G will give us H' = (H minus one edge). Letting H be an expander graph with treewidth \theta(n), we see that H' has treewidth \theta(n) as well.
gphilip
CC BY-SA 2.5
2010-08-17T00:53:48.867Z
2010-08-17T00:53:48.867Z
David Eppstein
<p>Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible? </p>

<p>It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?</p>

<upper-bounds><treewidth>
How large a treewidth can a tree plus half the edges have?
gphilip
# How large a treewidth can a tree plus half the edges have?

(Asked by: username_0 on 2010-08-17)

Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?

It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?

**Tags:** upper-bounds, treewidth

---

## 2 answers

### Answer by username_2 on 2010-08-17. Score: 19 | Accepted answer

Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but Θ(n) is best possible, yes.

> **Comments:**
> **username_0**: Thanks, that answers my question.  To elaborate David's answer a bit, let H be a connected 3-regular graph on 2n vertices. H then has 3n edges. Let G be a tree on 2n vertices obtained by removing n+1 edges from H. Adding n of these edges back to G will give us H' = (H minus one edge). Letting H be an expander graph with treewidth \theta(n), we see that H' has treewidth \theta(n) as well.  

---

### Answer by username_1 on 2010-08-17. Score: 10

As David pointed out, you basically ask for bounds on the treewidth of a connected graph with average degree 3. For the more special case of 3-regular graphs, the following lower and upper bounds can be obtained. Denoting by pw(G) the pathwidth of a graph G, it is clear that

(1) tw(G) <= pw(G) for any graph G (as a path decomposition is a tree decomposition)

It is proved in [1] that

(2) For every \epsilon > 0, there exists an integer n\_0 such that for any 3-regular graph G on n >= n\_0 vertices, pw(G) <= n/6 + \epsilon\*n.

This gives you an upper bound of roughly n/6 on the treewidth of 3-regular graphs.

For an almost sure lower bound, I cite from [2]:

"As random cubic graphs almost surely have bisection width at least 0.101 n (Kostochka, Melnikov, 1992), they have almost surely no separator of size smaller than n/20"
and thus almost surely no tree decomposition of width smaller than n/20.

For a "sure" lower bound on the bisection width, [3] showed an infinite family of 3-regular graphs, such that each graph G=(V,E) in this family has bisection width at least 0.082 \* |V|.

[1] Fedor V. Fomin, Kjartan Høie: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb. 29(3): 777-791 (2008)

[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: New spectral lower bounds on the bisection width of graphs. Theor. Comput. Sci. 320(2-3): 155-174 (2004)

> **Comments:**
> **username_0**: Thank you, Serge. The bound via pathwidth is probably more accessible to me at this stage than the one via expander graphs; I haven't read either proof yet, though.  

---

