Sone of vertices of the infinite grid Z2 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)×(2n+1) square centered by the origin is less than 2n.
Prove that among the branches of the graph, exactly one has an infinite number of vertices.Time allowed for this problem was 90 minutes. combinatorics unsolvedcombinatorics