The famous star-comb lemma for infinite graphs states that if $S$ is a infinite set of vertices in a connected graph $G$, then $G$ contains either a comb with all teeth in $S$ or a subdivision of an infinite star with all leaves in $S$.

Here by comb I mean a graph that is a path with an additional leaf joined to each vertex of the path and by teeth I mean the leaves of the comb. A star is a complete bipartite $K_{1,\mathbb{N}}$.

I would like a theorem of the same kind that gives an unavoidable (induced) subgraph (or subdivision of a subgraph) for a finite graph $G$ that contains a large star (a graph $K_{1,n}$ with $n$ big) as a minor, but contains a big comb (the order of the comb is given by the length of the main path). In other words, $G$ has a large star minor but bounded maximum degree.


  • $\begingroup$ I'm sorry to hear that the star-comb lemma is so famous, because that means I must be extremely ignorant not to have heard of it. Please explain one thing to me. How can (a subdivision of) an infinite star have all its leaves in $S$ if "$S$ is a finite set of vertices"? $\endgroup$
    – bof
    Mar 19 '14 at 7:17
  • $\begingroup$ @bof It's so named in Diestel's book... except $S$ should be an infinite set of course. $\endgroup$
    – Casteels
    Mar 19 '14 at 12:05
  • $\begingroup$ you are right, $S$ is infinite, apologies $\endgroup$
    – TJIF
    Mar 19 '14 at 16:53

I'm not totally sure what you are looking for, but this result might be useful:

For any positive integer $r$, there is a positive integer $n$ so that any connected graph of order at least $n$ contains either $K_r$, $K_{1,r}$ or $P_r$ as an induced subgraph.

This is easy enough to prove, and is Proposition 9.4.1 in Diestel. Of course if you relax to subgraphs, an easy corollary is that in a large enough graph you can find either a large star or a large path subgraph.

There are similar results for unavoidable topological minors of large 2-connected graphs, and unavoidable minors of large 3-connected, internally 4-connected, and 4-connected graphs.

  • $\begingroup$ I was thinking something like: for every positive integer $r$, there is some $n$ so that if a graph $G$ contains $K_{1,n}$ as a minor, then $G$ contains $K_{r}$, $K_{r,r}$ or a comb with $r$ leaves as an induced subgraph.. $\endgroup$
    – TJIF
    Mar 26 '14 at 1:41
  • $\begingroup$ I still don't really understand. $K_{1,n}$ itself has no large $K_r$, $K_{r,r}$ or comb. From your original post, it seems you are looking for a result about large graphs with NO $K_{1,r}$ minor. Isn't that exactly the result I've given? For every positive integer $r$, there is some $n$ so that if $G$ is a connected graph on $n$ vertices with no $K_{1,r}$ induced subgraph, then $G$ must have $K_r$ or $P_r$ as an induced subgraph. You can't get a comb here, because a large $P_r$ itself has no $K_{1,r}$ minor. $\endgroup$ Mar 26 '14 at 13:27
  • $\begingroup$ oh, I'm very very sorry. I meant that has a $K_{1,r}$ minor!! (in which case the three graphs are mentioned have a star minor of course) $\endgroup$
    – TJIF
    Mar 26 '14 at 13:35
  • $\begingroup$ You will need some more conditions if you want to find something interesting then. A large connected graph with a $K_{1,r}$ minor could just be $K_{1,n}$, every minor of which is also a star... $\endgroup$ Mar 26 '14 at 13:43
  • $\begingroup$ well, if (connected) $G$ has big maximum degree (and has a big $K_{1,n}$ minor), it has a big $K_{1,n}$ or $K_{n}$ as induced subgraphs from Ramsey's theorem; if $G$ has bounded maximum degree, then my claim that it has the comb (or something close to a comb?) as an induced subgraph. Is that false? $\endgroup$
    – TJIF
    Mar 26 '14 at 14:23

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.