Question:
A graph has $ n $ vertices and $ e $ edges. What is the number of vertices in the spanning tree of that graph?
A graph has $ n $ vertices and $ e $ edges. What is the number of vertices in the spanning tree of that graph?
Show Hint
In a spanning tree, the number of vertices is the same as in the original graph.
Updated On: May 3, 2025
- \( |n - e| \)
- \( |n - e + 1| \)
- \( n \)
- \( e \)
Hide Solution
Verified By Collegedunia
The Correct Option is C
Solution and Explanation
A spanning tree of a graph with \( n \) vertices always has exactly \( n \) vertices. This is because a spanning tree is a subgraph that includes all the vertices of the original graph but without cycles and with the minimal number of edges.
Thus, the number of vertices in the spanning tree is \( n \).
Thus, the number of vertices in the spanning tree is \( n \).
Was this answer helpful?
0
0
Top Questions on Graph Theory
- A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on n vertices, \( n \) is _______.
- Dijkstra's algorithm fails for graphs with _______.
- Assume G is a simple undirected graph and some vertices of G are of odd degree. Add a node \( v \) to G and make it adjacent to each odd degree vertex of G, then the resultant graph is sure to be _______.
- A subgraph H of a graph G is called a clique if _______.
- For a given graph G having \( v \) vertices and \( e \) edges which is connected and has no cycles, which of the following statements is true?
View More Questions
Questions Asked in AP PGECET exam
- Given \( x_0 \neq 0 \), the iteration \[ x_{n+1} = \frac{1}{2} \left( -\frac{9}{x_n} + x_n \right), n \geq 0 { is a} \]
- AP PGECET - 2025
- Numerical Methods
- Suppose \( \sum_{n=1}^{\infty} a_n (x - 2)^n \) is convergent at \( x = -5 \), then it need not be convergent on which interval?
- AP PGECET - 2025
- Convergence tests
- The set of all critical points of the function \( f(x) = |x^2 - 1| \) on \( [-2, 2] \) is ...........
- AP PGECET - 2025
- Calculus
The surface integral \( \int_S x^2 \, dS \) over the upper hemisphere
\[ z = \sqrt{1 - x^2 - y^2} \]
with radius 1 is ..........- AP PGECET - 2025
- Calculus
- Consider the system of equations:
\[ x + 2y - z = 3 \\ 2x + 4y - 2z = 7 \\ 3x + 6y - 3z = 9 \]
Which of the following statements is true about the system?
- AP PGECET - 2025
- Linear Algebra
View More Questions