A connected graph G has 32 vertices. How many vertices does a spanning tree of G have?
A) 30
B) 31
C) 32
D) 33

Name: A connected graph G has 32 vertices. How many vertices does a spanning tree of G have? A) 30 B) 31 C) 32 D) 33
Brand: Quizplus
Rating: 4.7 (43 reviews)

Question

Quizplus · Accepted Answer

A spanning tree of a graph G is a subgraph that includes all of the vertices of G and is a tree. Since a tree with n vertices has exactly n-1 edges, and the question asks for the number of vertices, the spanning tree of a graph with 32 vertices also has 32 vertices.

A Connected Graph G Has 32 Vertices