Tree questions often combine the n-1 edge test with distance, eccentricity, diameter, radius and center. In this eight-vertex tree, the eccentricities are (5,4,3,4,3,4,5,4), so its diameter is 5, radius is 3 and center is {C,E}. Use GATE CS Exam Preparation for the wider route, and read the Graph Theory overview for adjacent concepts.
What makes an undirected graph a tree
A finite undirected simple graph is a tree if it is connected and has no cycle. The smallest tree has one vertex and no edge. Terms such as parent, child and level belong to rooted trees, so they are not part of this unrooted definition.
For a graph with n vertices, each of these is an equivalent complete test:
It is connected and has
n-1edges.It is acyclic and has
n-1edges.Exactly one simple path joins every pair of vertices.
It is connected, and removing any edge disconnects it.
It is acyclic, and adding any missing edge creates exactly one cycle.
Use each condition as a complete test. Having n-1 edges alone does not prove a tree. For n >= 2, every tree has at least two leaves, and its degree sum is 2(n-1). Engineering Mathematics for GATE provides a structured route through this discrete mathematics foundation.
Fix one tree and audit its structure
Let T denote the tree used for all calculations:
V = {A,B,C,D,E,F,G,H}
E = {AB,BC,CD,CE,EF,FG,EH}
Here n=8 and m=7=n-1. The degrees are deg(A)=1, deg(B)=2, deg(C)=3, deg(D)=1, deg(E)=3, deg(F)=2, deg(G)=1 and deg(H)=1. Their sum is 14=2m. Therefore, the leaves are {A,D,G,H}, while {B,C,E,F} are internal vertices.
Every vertex is reachable from C, so the graph is connected. There is exactly one simple path from C to every other vertex, and likewise between every pair, so it is acyclic by the unique-path test. Removing CE splits it into {A,B,C,D} and {E,F,G,H}. Adding the missing edge DH creates exactly the cycle D-C-E-H-D, whose length is 4.
Distance and eccentricity, row by row
The distance d(u,v) is the number of edges on the unique path from u to v. It is not the number of vertices written on that path. The eccentricity of a vertex is its greatest distance to any vertex:
e(v) = max d(v,u) over all vertices u.
The complete distance table for our tree is symmetric:
From / to | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|
A | 0 | 1 | 2 | 3 | 3 | 4 | 5 | 4 |
B | 1 | 0 | 1 | 2 | 2 | 3 | 4 | 3 |
C | 2 | 1 | 0 | 1 | 1 | 2 | 3 | 2 |
D | 3 | 2 | 1 | 0 | 2 | 3 | 4 | 3 |
E | 3 | 2 | 1 | 2 | 0 | 1 | 2 | 1 |
F | 4 | 3 | 2 | 3 | 1 | 0 | 1 | 2 |
G | 5 | 4 | 3 | 4 | 2 | 1 | 0 | 3 |
H | 4 | 3 | 2 | 3 | 1 | 2 | 3 | 0 |
Take the maximum in each row. This gives e(A)=5, e(B)=4, e(C)=3, e(D)=4, e(E)=3, e(F)=4, e(G)=5 and e(H)=4.
For example, the distances from C to A,B,C,D,E,F,G,H are 2,1,0,1,1,2,3,2. The largest is 3, reached at G, so e(C)=3.
Diameter, radius and center from the same values
The diameter is the largest eccentricity, the radius is the smallest eccentricity, and the center contains every vertex whose eccentricity equals the radius:
diam(T)=max e(v), rad(T)=min e(v), C(T)={v:e(v)=rad(T)}.
Our row maxima therefore give diam(T)=5, rad(T)=3 and C(T)={C,E}. The path A-B-C-E-F-G is a diameter path. It lists six vertices but contains five edges, so its length and d(A,G) are both 5. Its two middle vertices are C and E, exactly the center found from eccentricities.
A tree has either one center or two adjacent centers, located at the midpoint of any diameter path. The values also pass the general check 3 <= 5 <= 2x3. For a tree, rad(T)=ceil(diam(T)/2)=ceil(5/2)=3. Since the diameter is odd, diam(T)=2rad(T)-1, and this example has two centers. The radius cannot be 2.5 because graph distance is an integer edge count.
Find the answer faster without every distance row
For a tree, use the two-sweep method. Start at any vertex, say D. A farthest vertex is G, at distance 4. Start again from G; its farthest vertex is A, at distance 5. The recovered path G-F-E-C-B-A is a diameter, so the diameter is 5. Its two middle vertices, E and C, give the center.
A branch that merely looks longest is not proof. The endpoints must have the greatest distance in the whole tree. Diameter endpoints are leaves, but not every pair of leaves forms a diameter: d(D,H)=3, while d(A,G)=5.
On paper, mark leaf-to-leaf distances, retain the largest, then move inward equally from both endpoints. Moving two edges from A reaches C; moving two from G reaches E. The remaining edge CE shows that the center has two vertices.
Traps and counterchecks for plausible wrong answers
Counting vertices on a path.
A-B-C-E-F-Gshows six vertices, but its length is5because path length counts edges.Using
floor(diameter/2). Herefloor(5/2)=2, but no vertex has eccentricity2. The radius isceil(5/2)=3.Choosing the highest-degree vertex as the center. Both
CandEhave degree3, but degree alone does not define center. A center minimises the farthest-vertex distance.Treating
n-1edges as a complete proof. On{1,2,3,4}, the edges{12,23,31}givem=3=n-1, yet they form a triangle and leave vertex4isolated. The graph is not connected, so it is not a tree.Confusing unrooted and rooted trees. Our tree has no designated root and no left or right child. Its properties come from undirected paths and distances.
How questions combine properties and distances
A question can ask for several facts from one figure. In our tree, the leaves are {A,D,G,H}, the edge check is 7=8-1, e(D)=4, and the center is {C,E} because both vertices have the minimum eccentricity 3.
Now modify the graph carefully. Delete leaf H and edge EH. The diameter remains 5 along A-B-C-E-F-G, the radius remains 3, and the center remains {C,E}. Instead, keep the original tree and attach a new leaf I to G. The new diameter path A-B-C-E-F-G-I has length 6; the radius remains 3, and the unique center becomes E. Recalculate all three values instead of trusting the appearance of the drawing.
Use the Graph Theory MCQs for mixed practice on tree properties and related graph concepts.
The short version and the next step
A tree is connected and acyclic.
An
n-vertex tree hasn-1edges.Eccentricity is one vertex's largest distance.
Diameter is the largest eccentricity.
Radius is the smallest eccentricity, and its achievers form the center.
Here the eccentricities are (5,4,3,4,3,4,5,4), so diameter=5, radius=3 and center={C,E}. Use this same audit on every figure. Continue with GATE Guidance by Sanchit Sir for the broader preparation route.
