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!


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.