A spanning tree of a connected graph with V vertices must have which property?

All V vertices, connected, no cycle, V-1 edges

All V vertices, V edges, exactly one cycle

All V vertices with every pair directly joined

Only the vertices on the shortest path, V-1 edges

Which spanning tree is the minimum spanning tree?

The one with the smallest sum of edge weights

The one with the shortest path between two chosen vertices

The one that starts with the smallest-weight edge only

How does Kruskal's algorithm choose edges?

Sort edges by weight and add each one unless it forms a cycle

Grow one tree from a start vertex, always taking the nearest vertex

Add the heaviest edges first and remove cycles later

Take edges in the order they are given in the graph

Why is edge C-E (5) rejected in the given graph?

C and E are already connected through F (cycle C-E-F)

Vertex E has already been used twice

It would give more than 5 edges

What is the MST of the graph and its cost?

E-F, A-B, C-F, A-C, D-F with cost 21

E-F, A-B, C-F, C-E, D-F with cost 20

E-F, A-B, C-F, A-C, B-D with cost 23

E-F, A-B, C-F, A-C, A-F with cost 19

2070 Bhadra · 5 marks

MST definition; Kruskal's MST on 6-vertex graph

Short answer

A minimum spanning tree is a spanning tree with the smallest total edge weight. Kruskal's algorithm on this graph yields edges E-F(1), A-B(2), C-F(3), A-C(6), D-F(9), with minimum cost = 21.

What do you mean by minimum spanning tree? Find out the minimum spanning tree for given graph using Kruskal's algorithm. [Figure: undirected weighted graph on vertices A, B, C, D, E, F with edges A-B 2, A-C 6, A-F 7, B-D 11, C-F 3, C-E 5, D-F 9, E-F 1]

Minimum spanning tree

A spanning tree of a connected undirected graph G with V vertices is a subgraph that contains all V vertices, is connected and has no cycle (exactly V−1 edges). For a weighted graph, the spanning tree whose sum of edge weights is the smallest is the minimum spanning tree (MST). It is used in network design (least cable, pipeline or road cost).

Kruskal's algorithm on the given graph

6 vertices, so 5 edges are needed. Edges sorted: E-F 1, A-B 2, C-F 3, C-E 5, A-C 6, A-F 7, D-F 9, B-D 11.

Step	Edge	Weight	Decision	Total
1	E-F	1	accept	1
2	A-B	2	accept	3
3	C-F	3	accept	6
4	C-E	5	reject (cycle C-E-F)	6
5	A-C	6	accept	12
6	A-F	7	reject (cycle)	12
7	D-F	9	accept (5th edge)	21

MST edges: E-F, A-B, C-F, A-C, D-F. Minimum cost = 21.

✓ Answer checked by Claude Opus 5.5 (high effort)

Kruskal's MST on 9-vertex graph · Data Structure and Algorithm, chapter 10 · asked 3×
Kruskal's MST on 7-vertex graph · Data Structure and Algorithm, chapter 10 · asked 3×
Kruskal's MST on graph A to G · Data Structure and Algorithm, chapter 10 · asked 3×
Spanning tree properties; Round Robin MST · Data Structure and Algorithm, chapter 10
Round Robin MST on 7-vertex graph · Data Structure and Algorithm, chapter 10
Kruskal's algorithm with example · Data Structure and Algorithm, chapter 10 · asked 3×

All Data Structure and Algorithm chapter 10 questions →

MST definition; Kruskal's MST on 6-vertex graph

Minimum spanning tree

Kruskal's algorithm on the given graph

Related questions