Caterpillar Graphs

Question

Here is a problem I have been working on: Find a tree T containing exactly 3 vertices that are not end vertices such that T is not a caterpillar. I have been told that this is possible, but I am stuck; I am convinced that this is not possible. Here is my "proof":

Suppose there exists a tree T with three non-end vertices and T is not a caterpillar. Since T is not a caterpillar, removing the end vertices will not produce a path. So let's remove all end vertices and let the resulting graph be P. Notice that the graph P must contain only three vertices that were not end vertices. Since P is not a path, a vertex must be repeated. Notice that the graph P cannot be disconnected because trees are connected. Thus we have a connected graph of order 3 that is not a path. It cannot be a cycle because trees are a-cyclic. Such a graph P is nonsense, right?

Any help will be appreciated.

Answer 1

I don't, offhand, see anything wrong with your claim, but it's possible that you have mis-transcribed the original assertion --- that might be worth checking. I honestly don't know whether the assertion you think you've been asked to prove is true or not. (It appears false to me, but I haven't had a second cup of coffee yet.) But I can offer comments on what you've said.

As for your proof, there are a few rough bits. You write "Notice that the graph P must contain only three vertices that were not end vertices." I think what you mean is "Observe that, by hypothesis, $P$ contains exactly three vertices (the non-end vertices of $T$), and some number of edges."

"Since $P$ is not a path, a vertex must be repeated." That's vague. I think you might want to say "Because $P$ is not a path, ..." Actually, I think you might want to skip this sentence.

"Notice that $P$ cannot be disconnected": perhaps better to say "Observe that because $T$ is a tree, the graph $P$ is connected."

Then you can come back to the former point, and say "The only connected non-path graph on three vertices is a triangle." Now you know the structure of $P$ explicitly, and it contradicts your assumptions, so you're done.

Answer 2

As pointed out by John Hughes your claim is correct. On the other hand, notice that such tree exists if the not end-vertices are MORE than 3.

The above tree has FOUR vertices that are not end-vertices, and, by removing the end-vertices (and the incident edges), we DO NOT obtain a path graph. Therefore it is not a caterpillar tree.