Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I believe this is true:

Suppose $G$ is a graph. If $G$ has a subdivision of a large binary tree, prove that $G$ has an induced subgraph which is a subdivision of a large binary tree or the line graph of a subdivision of a large binary tree.

However, I think it is very difficult to prove in general, so I was hoping to do it for the case when $G$ has bounded treewidth (or say really small treewidth). Any ideas for those cases? Thank you!

[EDIT: I initially forgot the word subdvision in the question]

[EDIT2: PROVED, someone can delete]

share|improve this question
Why don't you just post a brief description of your answer, instead of requesting deletion? –  S. Carnahan Apr 13 at 6:13
Sure, i'll do that in a bit –  Cosmin Pohoata Apr 13 at 17:16

1 Answer 1

I'll just give a very brief sketch.

Find a large subdivided binary tree $T$ with branch vertices far apart and minimize its number of edges. This should be possible by tweaking 'far apart' and 'large' in accordance with the tree width.

Every edge spanned by $T$ but not in $T$ lies in the neighbourhood of a branch vertex $v$ of $T$. Case analysis gives desired structures locally:

  • one edge in $N(v)$: it's the linegraph of a subdivided claw
  • two edges in $N(v)$: remove $v$ it's a subdivided claw
  • three edges in $N(v)$: remove $v$ it's the linegraph of a subdivided claw

Now you have large graph $T$ that is a mixture of a subdivided binary tree and a linegraph of a subdivided binary tree. Since it is large enough you find branch vertices of the same type often enough.

Sorry, I had a longer answer that my pc forgot about. I'll elaborate if you have further question.

share|improve this answer
Sorry, I edited the question - I meant something else. You are of course right for what I initially wrote. –  Cosmin Pohoata Feb 17 at 18:24
I think there is another counterexample for this version too: Start with a triangle. i) add an edge to every vertex of degree one. ii) add a triangle to every vertex of degree 2. repeat i) and ii) until your graph is large enough. Basically, the graph looks like a binary tree, but every vertex is blown up to be a triangle. –  user125315 Feb 18 at 11:48
Sorry, you start with a triangle and add an edge to every vertex of degree one? –  Cosmin Pohoata Feb 18 at 18:04
Yeah, that needed to be 'two'. So you have a triangle, at every vertex you add an edge to some new vertex. Now you have a triangle, plus three leaves. For every vertex of degree one (the three new vertices) you add one triangle and identify one vertex of the first triangle with the first leaf, one vertex of the second triangle with the second leaf. Same for 'three'. –  user125315 Feb 18 at 20:02
that's nice; can we say something about the induced subgraphs however? it pretty much looks like there's no other bad graphs –  Cosmin Pohoata Feb 19 at 6:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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