# Similar to star-comb lemma but finite graphs

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.

Thanks!

• 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"?
– bof
Mar 19 '14 at 7:17
• @bof It's so named in Diestel's book... except $S$ should be an infinite set of course. Mar 19 '14 at 12:05
• you are right, $S$ is infinite, apologies
– 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.

• 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..
– TJIF
Mar 26 '14 at 1:41
• 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. Mar 26 '14 at 13:27
• 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)
– TJIF
Mar 26 '14 at 13:35
• 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... Mar 26 '14 at 13:43
• 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?
– TJIF
Mar 26 '14 at 14:23