Determine the formula for the toughness of a tree

294 Views Asked by At

Determine the formula for the toughness of a tree

Here is what I got so far.

Since every tree $T$ has at least 2 leaves, if we remove any vertex that adjacent to one of these leaves, we will get a disconnected graph, so the vertex cut $S$ of $T$ has at least one vertex, and $k(G-S) \geq 2$. Note that

$$\frac{|S|}{k(G-S)} \geq t$$

So the toughness $t(T)= \frac{1}{2}$? this just doesn't make any sense.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $T$ be a tree and let $\Delta(T)$ denote the maximum degree of the vertices of $T$. Note that in a tree, removing a vertex of degree $k$ will create $k$ connected components. So $t(T) \leq \frac{1}{\Delta(T)}$. It should not be too hard to prove that this is in fact an equality.