graph theory
I am going through available posts on this.
So diameter of graph:- Length of the longest distance between any two nodes.By distance it mean number of edges.
And diameter of tree :- the number of nodes on the longest path between any two leaf nodes
My question is as tree is a graph,so why can't we use same definition as of diameter of graph in tree.Are these totally different concepts?
This is what the graph looks like in the $n-1=9$ case:
A spanning tree is a subgraph that is both (a) a tree and (b) contains every edge.
Here's an example of a spanning tree in the above graph:
There will be many others. The task set in the question is to find examples of spanning trees of diameter $d$ for $d \in \{2,3,\ldots,n-1\}$, for all $n \geq 1$.
Hint: The brown edges in the following diagram illustrate examples of spanning trees of diameter $2,\ldots,6$, respectively, in the case $n-1=6$.
I suggest you try to generalize this construction. (Note the diameter $n-2$ case is special.)
So when they say the 'maximum distance' between two points, they mean you choose $(x,y)$, find $d(x,y)$ which is the minimum length of the path between them, and then define the diameter $d_G=\sup_{x,y\in V(G)}d(x,y)$. That will give you $3$ here and not $5$. You see, the distance itself is already defined as the minimum path length, so you cannot change that. What you can do is find the maximum of this minimum over all pairs of points.
Best Answer
You can use the same definition for trees. The two definitions you gave agree in the case of trees, since the longest path between two nodes will always be between two leaves (otherwise, you could extend the ends until you hit a leaf).
It's true that you link to a definition of tree diameter which counts nodes in the longest path, rather than edges. I think this is just an instance of the usual definition churn--different people have different ideas about what length means, and you always have to make sure you're on the same page.