Register

CMI2016-A-9

• recategorized by
1,298 views
2 2 votes

ScamTel has won a state government contract to connect $17$ cities by high-speed fibre optic links. Each link will connect a pair of cities so that the entire network is connected-there is a path from each city to every other city. The contract requires the network to remain connected if $any$ single link fails. What is the minimum number of links that ScamTel needs to set up?

  1. $34$
  2. $32$
  3. $17$
  4. $16$

2 Answers

Best answer
2 2 votes

Answer: C. $\mathbf {17}$

Explanation:

If all the cities are connected in a loop using $17-\text{Links}$, and if even a single link fails the loop can still be traversed using the other path.

$\therefore$ Connecting cities using $16-\text{Links}$ or less would not be sufficient because with just $16$ Links it would become a spanning tree that would consist of an only single path and will get disconnected even if a single link fails.

• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · CMI2016-A-8Next → · CMI2016-A-10
← Previous in category · CMI2016-A-5Next in category → · CMI2016-B-2a
Position:
Show:

Related questions

2 2 votes
2 answers 2 answers
1.2k
1.2k views
go_editor asked Dec 30, 2016
1,190 views
CMI2016-B-3
An undirected graph can be converted into a directed graph by choosing a direction for every edge. Here is an example:Show that for every undirected graph, there is a way...
1 1 vote
1 1 answer
833
833 views
go_editor asked Dec 30, 2016
833 views
CMI2016-B-2b
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $length$ of such a path (respectively ...
1 1 vote
2 2 answers
937
937 views
go_editor asked Dec 30, 2016
937 views
CMI2016-B-2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex is repeated. The $\textit{length}$ of such a path (resp...
2 2 votes
2 answers 2 answers
907
907 views
go_editor asked Dec 30, 2016
907 views
CMI2016-A-5
A dodecahedron is a regular solid with $12$ faces, each face being a regular pentagon. How many edges are there? And how many vertices?$60$ edges and $20$ vertices$30$ ed...