Consider an art gallery whose walkways are shown as lines in the diagram. A black dot represents a junction of two walkways. A guard may be placed at a junction to watch over the walkways that join at that junction. The minimum number of guards needed to watch all the walkways is ________.

Question

The primary purpose of mine ventilation is to:

Answer 1

The diagram is a loop of 5 junctions connected by 5 walkways: a top junction, a left-upper and right-upper junction below it, and a left-bottom and right-bottom junction below those, closed off by a walkway along the base. A guard placed at a junction watches every walkway meeting there, so the goal is to find the smallest number of junctions that between them touch all 5 walkways.

Trying 2 guards: Any single junction touches only 2 walkways in this diagram, since exactly two walkways meet at each junction. Two guards can therefore touch at most 4 walkway-ends between them without overlap, but there are 5 walkways to cover, and checking every pair of junctions shows at least one walkway is always left with neither end guarded. So 2 guards are never enough.
Trying 3 guards: Pick the top junction, the left-bottom junction and the right-bottom junction. The top junction covers the two walkways running down from it. The left-bottom junction covers the walkway coming down to it and the base walkway. The right-bottom junction also covers the base walkway and the walkway coming down to it. Every one of the 5 walkways now has at least one end guarded.
Checking if fewer than 3 can ever work: Since the diagram forms one single closed loop of 5 junctions and 5 walkways with no shortcuts, skipping guards on alternate junctions the way you could on a loop with an even number of junctions always leaves one walkway with both ends unguarded when the loop length is odd, like 5 here. This confirms 3 is the smallest number that works.

So the minimum number of guards is 3, matching option (B).

Let's summarize:

Placing a guard at a junction is the same as picking that vertex to cover every walkway touching it.
The diagram is one closed loop of 5 junctions, an odd-length loop.
An odd loop of 5 junctions always needs at least 3 guards, and 3 is achievable, so 2 can never be enough.

The minimum number of guards needed is 3.

Answer 2

The diagram is a loop of 5 junctions connected by 5 walkways: a top junction, a left-upper and right-upper junction below it, and a left-bottom and right-bottom junction below those, closed off by a walkway along the base. A guard placed at a junction watches every walkway meeting there, so the goal is to find the smallest number of junctions that between them touch all 5 walkways.

Trying 2 guards: Any single junction touches only 2 walkways in this diagram, since exactly two walkways meet at each junction. Two guards can therefore touch at most 4 walkway-ends between them without overlap, but there are 5 walkways to cover, and checking every pair of junctions shows at least one walkway is always left with neither end guarded. So 2 guards are never enough.
Trying 3 guards: Pick the top junction, the left-bottom junction and the right-bottom junction. The top junction covers the two walkways running down from it. The left-bottom junction covers the walkway coming down to it and the base walkway. The right-bottom junction also covers the base walkway and the walkway coming down to it. Every one of the 5 walkways now has at least one end guarded.
Checking if fewer than 3 can ever work: Since the diagram forms one single closed loop of 5 junctions and 5 walkways with no shortcuts, skipping guards on alternate junctions the way you could on a loop with an even number of junctions always leaves one walkway with both ends unguarded when the loop length is odd, like 5 here. This confirms 3 is the smallest number that works.

So the minimum number of guards is 3, matching option (B).

Let's summarize:

Placing a guard at a junction is the same as picking that vertex to cover every walkway touching it.
The diagram is one closed loop of 5 junctions, an odd-length loop.
An odd loop of 5 junctions always needs at least 3 guards, and 3 is achievable, so 2 can never be enough.

The minimum number of guards needed is 3.

Consider an art gallery whose walkways are shown as lines in the diagram. A black dot represents a junction of two walkways. A guard may be placed at a junction to watch over the walkways that join at that junction. The minimum number of guards needed to watch all the walkways is ________.

Show Hint

The Correct Option is B

Solution and Explanation

Questions Asked in GATE MN exam