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 \)
Show 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 AP PGECET Computer Science & Information Technology Questions
- The number of multiplications needed to find $ x^{32} $ when $ x $ is given, is
- How many terms will there be in the expansion of $ (x + y + z)^5 $?
- How many 5-digit numbers can be formed with the digits 0, 1, 2, 3, 4, with no digit being repeated?
- What is the generating function for $ a_r $, where $ a_r $ is the number of integral solutions for the equation $$ a + b + c = r \quad \text{with} \quad 0 \leq a, b, c \leq 3? $$
- What is the value of $ f(5) $ where $ f(n) $ is recursively defined as $ f(n) = n \times (n-1) $ for $ n>1 $ and $ f(1) = 2 $?
View More Questions
Top AP PGECET Graph Theory Questions
What are the in-degree and out-degree of vertex 4?
- Which of the following statements is true?
- What is the chromatic number of a bipartite graph?
- How many edges will a tree with $ n $ vertices have?
What is the minimum number of colours required to colour the following graph?
View More Questions
Top AP PGECET Questions
- If 125V is applied across a 250V, 100W incandescent bulb, the power consumed will be _____ .
- The power consumed by a coil is 300 watts when connected to a 30V DC source and 108 watts when connected to a 30V AC source. The reactance of the coil is ____ .
The supply voltage magnitude \( |V| \) of the circuit shown below is ____ .
A two-port network is defined by the relation
\(\text{I}_1 = 5V_1 + 3V_2 \)
\(\text{I}_2 = 2V_1 - 7V_2 \)
The value of \( Z_{12} \) is:- Which of the following theorems is the dual of Norton’s theorem?
View More Questions