# Maximum Treewidth of a Graphs with $m$ Edges

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function?

$\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has$m$edges}\}$.

Clearly $\alpha(m) = \Omega(\sqrt{m})$, which is attained by cliques with $\Omega(\sqrt{m})$ vertices and by by $\Omega(\sqrt{m})\times \Omega(\sqrt{m})$ grids.

Is this also the maximum?

• cubic expanders have linear treewidth. – PsySp Sep 12 '17 at 12:38
• @PsySp Could you please post this as an answer with a reference to the fact that expanders have linear treewidth? – Springberg Sep 12 '17 at 22:31

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in:
The best known upper bound of the treewidth in terms of the number of edges of a graph is as follows: the pathwidth (and therefore also the treewidth) of any graph on $n$ vertices and $m$ edges is at most $13 m / 75 + o(n)$.