recategorized by
889 views
1 votes
1 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$
recategorized by

2 Answers

Best answer
2 votes
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
Answer:

Related questions

1 votes
1 votes
2 answers
1
go_editor asked Dec 30, 2016
759 views
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 votes
1 votes
2 answers
4
go_editor asked Dec 30, 2016
549 views
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...