Ответ:

Красные клетки образуют конечный граф: каждая красная клетка должна иметь ровно двух красных соседей по стороне. Значит, среди красных клеток должен быть цикл. Самый короткий цикл на клетчатой сетке — квадрат из четырёх клеток.

Такой пример существует: достаточно закрасить все клетки блока размером 2 × 2. У каждой из четырёх клеток тогда ровно два красных соседа.

Ответ: 4