Lemma: Any graph of order (number of vertices ) with at least edges has a cycle.
Proof: The heuristic is this:

Vertices of degree 1 are useless cause they can't form cycles.

So the idea is to keep deleting vertices of degree 1 along with its incident edge. This motivates strong induction. Base case is trivial.

Case 1: All vertices have degree at least consider the longest path of the graph: Note that for each its set of neighbors must be within this path, otherwise there exists a neighbor of say such that Add that to the path to obtain a longer path, contradiction. Therefore, because has at least neighbors in this maximal path, one of its neighbors must be Then we have a cycle, as desired.

Case 2: At least one vertex has degree delete vertices of degree and each of their incident edges. Afterwards we've still maintained the condition, but the number of vertices has gone down. Apply strong induction hypothesis and we're done.

Back to problem: Set the points of the problem as vertices in graph and connect two vertices and color it blue if belong to the same row and red if they belong to the same column. It's not hard to see there're at least blue edges and red edges of our graph. Since there're at least edges and vertices, we must have a cycle.

Unfortunately, this cycle might be monochromatic - all the edges of the same color. In particular, we want to force a cycle to not be monochromatic. Let's redefine the way we defined an edge as follows:

Connect vertex to and iff is in the same row as but is in the same column as In other words, our edges come in pairs: in the shape of an Define to be the joint of the Note that we can't have a cycle of length since we can't have and be in the same row or column.

Therefore, every vertex of nonzero degree must have at least a blue and a red edge. It suffices to show there're at least such shapes. We apply a heuristic similar to our lemma:

Vertices that cannot be the joint of an called useless. In other words, a useless vertex will be completely alone in either its row or column.

If there're at most shapes, there're at least useless vertices. Now the claim is that at least one of the useless vertices will have exactly other vertex in its row and column combined. If we can find such a useless vertex, delete both the row and column its in, leaving us with a grid and points, and we can apply strong induction.

Otherwise, each useless vertex will have at least other vertices in its row or column and none in the other, so there's at least vertices in its row and column combined. But any vertex that's not useless is the joint of an shape, so there's also at least vertices in its row and column combined.

Then... rip.

Consider a bipartite graph partitioned into vertices representing columns and representing rows. Connect two vertices if their intersection includes one of the numbers. Since this graph is of order , by the lemma we can find a cycle (even cycle of length at least cause the graph is bipartite), and it's not hard to see this cycle is equivalent to our condition.