GATE 2019 CS – Question 59
Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
Each machine is attached to a switch port. If $k$ switches are connected together as a **tree** (to keep the network connected with the fewest links), $k-1$ cables join them, and each cable uses a port on **both** ends, so $2(k-1)$ ports are used for the switch-to-switch links.
Ports left for machines: $8k-2(k-1)=6k+2$. We need $6k+2\ge15$:
- $k=2$: $14<15$, not enough.
- $k=3$: $20\ge15$, enough.
Minimum number of switches $=\mathbf3$.