Consider an array of points. For a subset of the edges of this array (i.e. the lattice edges), we denote by the set of vertices of and by the set of connected components of . For each natural number , prove that
(For a set , by we mean the number of elements of ).
Solution
First we prove the lower bound. Throughout the solution, we denote by and the number of vertices and edges of the -th connected component, respectively. Each lattice point has 4 adjacent lattice points, and so the degree of each vertex in a connected component is at most 4. Clearly, the degree of the rightmost vertex in each row of a connected component is at most 3 and similar statement holds for the leftmost vertex in each row, and the topmost and the bottommost vertex in each column of a connected component. Thus, we have at least 4 vertices of degree 3 and so
Summing these inequalities for all connected components yields
And this implies the left inequality.
Now we go to the right inequality. We know that there are vertices and edges in an array of points. Let be the greatest positive integer such that . So we can write , where is an integer. We will introduce a graph with edges, satisfying the right inequality. Firstly, consider an square, which has edges. If , we start to add some edges to the square. Suppose that the point is the leftmost point of the top side of the square. We add the edge connecting to . Then edges connecting to and . In the same manner, if we need more edges we choose the next edge on the square perimeter (counterclockwise) and add two edges to the graph using that edge. Let be the number of sides in the square perimeter, which have been used in our process. Thus, we have added new vertices for constructing edges. We know . Therefore, we have vertices in one connected component. So we must prove
Which is in turn equivalent to
If , the inequality is obvious. And if , the inequality will be which is again true because and so . So the assertion is proved.