in Graph Theory retagged by
421 views
3 votes
3 votes

The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a connected subgraph having the same six vertices and no cycles. How many edges must be deleted?

in Graph Theory retagged by
421 views

2 Comments

1
1

$ \large{\colorbox{yellow}{Detailed video solution of this question with direct time stamp}}$
All India Mock Test 2 - Solutions Part 3

1
1

1 Answer

6 votes
6 votes
The easiest way to do this is to play around, I think. One, two, or three edges don’t seem to be enough, but removing four edges gives us a straight graph on six vertices.

Note that a connected graph with no cycle is called a tree. $A$ tree on n vertices has $n-1$ edges. We need to delete edges from the given graph so that only $5$ edges remain. Hence, $4$ edges must be deleted.
edited by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true