MathDB

Sone of vertices of the infinite grid

\mathbb{Z}^{2}

are missing. Let's take the remainder as a graph. Connect two edges of the graph if they are the same in one component and their other components have a difference equal to one. Call every connected component of this graph a branch. Suppose that for every natural

n

the number of missing vertices in the

(2n+1)\times(2n+1)

square centered by the origin is less than

\frac{n}{2}

. Prove that among the branches of the graph, exactly one has an infinite number of vertices.
Time allowed for this problem was 90 minutes.

Problem Statement