IAE Academy

GATE 2026 IN GA Q.3: solution and answer

GATE 2026 · INGA Q.3 · 1 mark · MCQ

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 ________.

GATE 2026 IN GA question 3: A closed house-shaped pentagon drawn with 5 straight lines and 5 black dots (junctions) at its corners.Tap to open full size
Figure from the GATE 2026 IN paper. It is part of the question.
Figure description

A closed house-shaped pentagon drawn with 5 straight lines and 5 black dots (junctions) at its corners. The dots are: one at the top centre (apex); one at the upper left and one at the upper right, both at the same height below the apex; one at the bottom left directly below the upper-left dot; one at the bottom right directly below the upper-right dot. Lines: apex to upper-left (slanting down to the left); apex to upper-right (slanting down to the right); upper-left straight down to bottom-left (vertical); upper-right straight down to bottom-right (vertical); bottom-left to bottom-right (horizontal). No other lines, no labels. Every junction joins exactly two walkways.

  1. (A)

    2

  2. (B)

    3

  3. (C)

    4

  4. (D)

    5

Answer and solution

ANSWER

The minimum number of guards is 3, option (B).

Official answer: BSource: Official answer key, GATE 2026 IN (IIT Guwahati)

  1. Model the gallery as a graph. The junctions are vertices and the walkways are edges. The figure is a closed house-shaped pentagon, so it is a 5-cycle with 5 vertices and 5 edges, and every vertex has degree 2.

  2. A guard at a junction watches exactly the walkways that meet there, so each guard watches exactly 2 walkways. We need the smallest set of junctions that touches every walkway. In graph terms this is a minimum vertex cover.

  3. Lower bound: 2 guards watch at most walkways, but there are 5. So at least guards are needed.

  4. Now show that 3 guards are enough. Label the junctions T (apex), L and R (upper left and upper right), and BL and BR (bottom left and bottom right). Place guards at T, BL and BR.

  5. Check the cover. T watches T–L and T–R. BL watches L–BL and BL–BR. BR watches R–BR (and BL–BR again). All 5 walkways are watched.

  6. The minimum number of guards is 3, which is option (B).

KEY IDEA

Treat the walkways as the edges of a 5-cycle and the junctions as its vertices. Each guard covers only the 2 edges at his junction, so covering 5 edges needs at least guards, and 3 well-placed guards (apex plus both bottom corners) do the job.

WATCH OUT FOR

Answering 2 by putting guards at two opposite-looking corners, such as the two upper side junctions, and forgetting that the bottom walkway is then unwatched. Two guards can cover at most 4 walkways, and there are 5. The other trap is thinking a guard is needed at every junction (5), when a guard at one junction also covers both walkways ending there.

From the GATE 2026 IN paper. Every question of this paper · Download the full paper · All 41 Reasoning questions, with notes

More Reasoning questions