Tree questions often hide one of four invariants inside long wording. A tree on \(n\) vertices has \(n-1\) edges, degree sum \(2(n-1)\), exactly one simple path between every vertex pair, and one or two adjacent centers of minimum eccentricity. The challenge is recognising the useful fact. Solve each question by identifying the relevant invariant or method. Attempt each before reading its explanation, and write that invariant beside the options. This turns a complicated stem into a checkable argument. A linked question heading opens either the matching question or the broader tree practice set.
Tree definitions, eccentricity, radius, diameter and center
A tree is a connected, acyclic, undirected graph. Equivalent checks are \(|E|=|V|-1\) plus connectivity or acyclicity, and exactly one simple path between every vertex pair.
For vertex \(v\), \(e(v)=\max_u d(v,u)\). Diameter is \(\max_v e(v)\), radius is \(\min_v e(v)\), and the center contains the vertices with eccentricity equal to the radius.
On path \(v0-v1-v2-v3-v4-v5\), the eccentricities are \(5,4,3,3,4,5\). Thus diameter is \(5\), radius is \(3\), and adjacent vertices \(v2,v3\) are the centers. A tree has one center for even diameter and two adjacent centers for odd diameter. For wider practice, use Graph Theory MCQs: 12 Solved Euler, Coloring and Trees.
Distance transforms and degree sums
Question 1: Bound the diameter after adding distance-two edges
Let \(G=(V,E)\) be an undirected unweighted connected graph. The diameter of \(G\) is defined as: \(\text{diam}(G)=\displaystyle \max_{u,v\in V} \{\text{the length of shortest path between $u$ and $v$}\}\) Let \(M\) be the adjacency matrix of \(G\). Define graph \(G_2\) on the same set of vertices with adjacency matrix \(N\), where \(N_{ij}=\left\{\begin{array} {lll} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.\) Which one of the following statements is true?
A. \(\text{diam}(G_2)\leq\lceil \text{diam}(G)/2\rceil\)
B. \(\lceil \text{diam}(G)/2\rceil<\text{diam}(G_2)< \text{diam}(G)\)
C. \(\text{diam}(G_2) = \text{diam}(G)\)
D. \(\text{diam}(G)< \text{diam}(G_2)\leq 2\; \text{diam}(G)\)
Answer: A. Since \(M^2\) detects length-two walks, \(G_2\) crosses a length-\(d\) shortest path in at most \(\lceil d/2\rceil\) edges, proving the bound after maximisation. On the six-vertex path, diameter falls from \(5\) to \(\lceil5/2\rceil=3\).
Question 2: Find the degree sum of a 10-vertex tree
Let \(T\) be a tree with 10 vertices. The sum of the degrees of all the vertices in \(T\) is ________
Options: none (NAT)
Answer: 18. The tree has \(10-1=9\) edges, so the handshake lemma gives degree sum \(2|E|=2\times9=18\). The tempting \(9\) is the edge count.
Parity arguments and line-graph counterexamples
Question 3: Force an odd degree outside a subset
Consider a set \(U\) of 23 different compounds in a Chemistry lab. There is a subset \(S\) of \(U\) of 9 compounds, each of which reacts with exactly 3 compounds of \(U\). Consider the following statements: I. Each compound in \(U \setminus S \) reacts with an odd number of compounds. II. At least one compound in \(U \setminus S \) reacts with an odd number of compounds. III. Each compound in \(U \setminus S \) reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?
A. Only I
B. Only II
C. Only III
D. None
Answer: B. Reactions form undirected edges, and \(S\) contributes degree sum \(9\times3=27\), while the total degree sum is even. The other 14 degrees therefore sum to an odd number, forcing at least one odd degree but not one parity for all.
Question 4: Decide which line-graph claim is always true
The line graph \(L(G)\) of a simple graph \(G\) is defined as follows: • There is exactly one vertex \(v(e)\) in \(L(G)\) for each edge \(e\) in \(G\). • For any two edges \(e\) and \(e'\) in \(G\), \(L(G)\) has an edge between \(v(e)\) and \(v(e')\), if and only if \(e\) and \(e'\) are incident with the same vertex in \(G\). Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
A. P only
B. P and R only
C. R only
D. P, Q and S only
Answer: A. Every edge of \(C_n\) meets its two neighbours, reproducing \(C_n\). Q fails for \(K_4\) with disjoint edges, R for planar \(K_{1,5}\) whose line graph is \(K_5\), and S for tree \(K_{1,3}\) whose line graph is a triangle.
Tree invariants, vertex counts and edge counts
Question 5: Compare two trees through a degree-sum invariant
Let \(G=(V, E)\) be a graph. Define \(\xi(G) = \sum\limits_d i_d*d\) , where id is the number of vertices of degree \(d\) in \(G\). If \(S\) and \(T\) are two different trees with \(\xi(S) = \xi(T)\) , then
A. \(|S| = 2|T| \)
B. \(|S| = |T| - 1\)
C. \(|S| = |T| \)
D. \(|S| = |T| + 1\)
Answer: C. Here \(\xi(G)\) is the degree sum, equal to \(2(n-1)\) for an \(n\)-vertex tree. Thus \(2(|S|-1)=2(|T|-1)\), so \(|S|=|T|\), though their shapes may differ.
Question 6: Maximize edges in an acyclic graph
What is the maximum number of edges in an acyclic undirected graph with n vertices?
A. n-1
B. n
C. n + 1
D. 2n-1
Answer: A. A forest with \(c\) components has \(n-c\) edges, maximised at \(c=1\). That gives a tree with \(n-1\) edges; one more creates a cycle.
A spanning tree is this connected, \(n-1\)-edge structure selected from a weighted graph. Minimum Spanning Tree for GATE: Kruskal and Prim explains how it is selected.
Diameter and connectivity
Question 7: Find the chromatic-number-to-diameter ratio of a hypercube
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
A. 1/(2n-a)
B. 1/n
C. 2/n
D. 3/n
Answer: C. Even and odd Hamming weights form a bipartition, giving chromatic number \(2\) for \(n\geq1\). Maximum Hamming distance is \(n\), attained by complements, so the ratio is \(2/n\).
Question 8: Classify an n-vertex, n-1-edge graph that is not a tree
A graph with n vertices and n-1 edges that is not a tree, is
A. Connected
B. Disconnected
C. Euler
D. A circuit
Answer: B. A connected graph with \(n\) vertices and \(n-1\) edges must be a tree, so this graph is disconnected. Its edge total also forces a cycle in at least one component, but the requested classification is disconnected.
Unique paths and degree distributions
Question 9: Identify a graph with exactly one path per vertex pair
In a graph G there is one and only one path between every pair of vertices then G is a
A. Path
B. Walk
C. Tree
D. Circuit
Answer: C. A path between every pair makes the graph connected, while any cycle would create two routes between some pair. It is therefore connected and acyclic, hence a tree, but not necessarily a path graph.
Question 10: Solve for the vertices and edges from three degree classes
A tree has \(2𝑛\) vertices of degree 1,\( 3𝑛\) vertices of degree 2, \(𝑛\) vertices of degree 3. Determine the number of vertices and edges in tree.
A. 12,11
B. 11,12
C. 10,11
D. 9,10
Answer: A. Here \(V=2n+3n+n=6n\), degree sum is \(2n+2(3n)+3n=11n\), and \(E=6n-1\). Then \(11n=2(6n-1)\), so \(n=2\), \(V=12\), and \(E=11\).
Leaf counts and the tree center
Question 11: Find the total vertices from the non-leaf degrees
A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph ?
A. 5
B. n – 3
C. 20
D. 11
Answer: D. With \(r\) leaves, \(V=r+4\) and degree sum is \(2(4)+3+2+r=13+r\). Since \(13+r=2(V-1)=2(r+3)\), \(r=7\) and \(V=11\).
Question 12: Find every center from vertex eccentricities
Consider the tree given below: Using the property of eccentricity of a vertex, find every vertex that is the center of the given tree:
A. d & h
B. c & k
C. g, b, c, h, j, m
D. c & h
Answer: D. A longest path such as \(a-b-c-h-i-j\) has five edges, so diameter is \(5\). Both \(c\) and \(h\) have eccentricity \(3\), the radius, while moving away from edge \(c-h\) increases the maximum distance.
Tree MCQ traps and score check
trap | wrong move | repair |
|---|---|---|
n-1 edges | conclude tree without checking connectivity or acyclicity | pair the edge count with one structural condition |
degree sum | use n-1 instead of 2(n-1) | separate edge count from degree sum |
unique path | confuse a tree with a path graph | unique paths allow branching |
center | choose every vertex on a diameter | select only the minimum-eccentricity middle vertex or adjacent pair |
Use your result to choose a revision target, not to estimate an official exam score. At 10-12 correct, redo Questions 1 and 12 unaided. At 7-9 correct, revise eccentricity and degree sums. At 0-6 correct, rebuild the four opening invariants.
The short version
For each tree question, first check connectivity and cycles, then write \(|E|=|V|-1\). Convert edges to degrees with the handshake lemma, and locate the center at the middle of a diameter. If the concepts still feel weak, follow GATE Guidance by Sanchit Sir. If you are ready to drill, use the GATE Test Series. To compare the wider route before choosing what to study next, review GATE CS Exam Preparation. Keep the four invariants visible while solving, and make every option justify itself.
