# treewidth and a complete k-vertex Subgraph

the question I'm concerned with is twofold.

First: I'm wondering about the relationship between complete subgraphs and $k$-degeneracy.

Let $G$ be an undirected simple graph.

A regular subgraph of magnitude $k+1$,does have a subgraph with vertices of degree $\delta(v) = k$ and therefore degeneracy of $k$. Does a graph have to have a regular subgraph of magnitude $k+1$ to have a degeneracy of $k$?

I have'nt found that fact online and therefore this seems very suspicious to me.

Secondly: I am supposed to prove that subdividing an edge in a graph( actually means splitting the edge and adding an inbetween vertex) does not change it's treewidth. And by virtue of that fact to conclude that $2$-degenerate graphs do have unbounded treewidth.

This seems truely strange to me, for e.g.:

Consider a triangle between vertices $u,v,w$. Now simply add a vertex $u'$ between $u$ and $v$, delete the edge $(u,v)$ and add two edges $(u,u')$ and $(u',v)$. The resulting graph is still $2$-degenrate and still has the same treewidth. But what i'm looking for actually is a constellation where i do increase the treewidth, without increasing the degeneracy?! right? I don't see any such opportunity.

Thanks a lot!

## 1 Answer

To answer your first question, no. Remember that a graph is $k$-degenerate if every subgraph has a vertex of degree at most $k$. So, for example, any cycle $C_n (n \geq 4)$ is 2-degenerate but it doesn’t contain a triangle. Note that the converse is also false as simply containing $K_{k+1}$ doesn't guarantee $k$-degeneracy (consider $K_{k+2}$).

For your second question, they are asking you to show that 2-degenerate graphs can have arbitrarily big treewidth. So for any $t$, take your favourite graph with treewidth $t$ and subdivide every edge. The resulting graph is 2-degenerate and also has treewidth $t$.