# In a $n \times n$ grid of points, choosing $2n-1$ points, there will always be a right triangle

$$\textbf{Question:}$$ Consider a $$n×n$$ grid of points. Prove that no matter how we choose $$2n-1$$ points from these, there will always be a right triangle with vertices among these $$2n-1$$ points.

This question indeed been posted beforeLink, but I was looking for an alternative solution using graph theory.

I have rephrased this question in terms of graph theory like this:

Given an $$n$$ by $$n$$ bipartite graph (where the vertices correspond to rows and columns), and if there is point with column $$c_i$$ and row $$r_j$$, we add an edge between $$(c_i,r_j)$$. Then the statement is equivalent to showing that with $$2n-1$$ edges in this graph, there must exist a path of length at least $$3$$.

I noticed some obvious facts like, if some vertex has degree more than 1 than the degree of its adjacent vertices will be $$1$$.

• If the problem has been posted before, please link to the old problem. – bof Jun 13 at 11:59
• @bof The right triangle will have bases parallel to the edges (There is no need to consider tilted right triangles) – Calvin Lin Jun 13 at 12:05

I strongly recommend that you read the other 2 solutions. They provide a much simpler proof.

Note: The setup only considers right triangle with bases parallel to the edges (which gives a path of length 3). This is sufficient to prove the problem. There isn't a need to account for tilted right triangles (which do not lead to a path of length 3).

Your observation of "if some vertex has degree more than 1 than the degree of its adjacent vertices will be 1" is the main crux.

Hint: Instead of focusing on $$n\times n$$ squares, relax the condition to $$n \times m$$ rectangles.

Prove the more general statement by induction:

With $$n, m \geq 2$$, for a $$(n, m)$$ bipartite graph with at least $$n + m - 1$$ edges, there is a path of length 3.

Base case: Prove it for $$n = 2$$ and all $$m\geq 2$$.
This is left to the reader (Consider the sum of degrees $$d(m_1) + d(m_2) = n + 1$$.)

Suppose for $$n, m \geq 3$$, that there is such a graph with no path of length 3 for $$n, m \geq 2$$.
There is a vertex (WLOG $$c_1$$) of degree $$d \geq 2$$.
If $$d = m$$, clearly any other edge not involving $$c_1$$ gives us a path of length 3.
If $$d = m-1$$, remove this vertex and all but 1 of it's neighbors, which gives us a $$(n, 2)$$ bipartite graph with $$n+m-1-(m-2) \geq n + 2 -1$$ edges.
Else, remove this vertex and all of it's neighbors, which gives us a $$(n-1, m - d)$$ bipartite graph with $$n+m - 1 - d \geq (n-1) + (m-d) - 1$$ edges.

Here's a simpler proof. Consider an $$m\times n$$ grid, $$m,n\ge2$$; let $$P$$ be a set of grid points, $$|P|=m+n-1$$; and assume for a contradiction that $$P$$ does not contain the vertices of a right triangle.

Let $$H$$ (respectively $$V$$) be the set of all points $$x\in P$$ such that no other point of $$P$$ lies on the same horizontal (respectively vertical) line as $$x$$. Plainly $$P=H\cup V$$. Since $$|P|=m+n-1$$, either $$|H|\ge m$$ or $$|V|\ge n$$.

Without loss of generality we suppose $$|H|\ge m$$. Since two points of $$H$$ can't lie on the same horizontal line, each of the $$m$$ horizontal lines contains a point of $$H$$ and therefore contains only one point of $$P$$, whence $$|P|=m$$ and $$n=1$$, contradicting our assumption that $$n\ge2$$.

P.S. A translation of this proof into graph theory would go like this. A bipartite graph has bipartition $$(V_1,V_2)$$, $$|V_1|=m\ge2$$, $$|V_2|=n\ge2$$, and it has $$m+n-1$$ edges. If there is no path of length $$3$$, then each edge has an endpoint of degree $$1$$. Therefore there are at least $$m+n-1$$ vertices of degree $$1$$, i.e., at most one vertex of degree $$\ne1$$. So either all vertices in $$V_1$$ have degree $$1$$, there are just $$m$$ edges, and $$n=1$$, or else all vertices in $$V_2$$ have degree $$1$$, there are just $$n$$ edges, and $$m=1$$.

• I don't understand one tiny part ,why is $P=H \cup V$ ? – Yes it's me Jun 13 at 14:46
• @Yesit'sme If there is a point $x\in V\setminus(H\cup V)$, then there is a point $y\in P\setminus\{x\}$ on the same horizontal line as $x$ (because $x\notin H$), and there is a point $z\in P\setminus\{x\}$ on the same vertical line as $x$ (because $x\notin V$), and then $x,y,z$ are vertices of a right triangle. – bof Jun 13 at 14:51
• Ah, nice observation of "each edge has an endpoint of degree 1". – Calvin Lin Jun 13 at 20:38

As you sugessted this graph $$G$$ is bipartite.

• If it has cycles, then each one has lenght $$2l$$ so the minimum lenght is $$4$$ and we are done.
• If there is no cycles then it must be tree (it can be easly verified if we say it has $$k$$ components, then in each component $$C_i$$ we have $$\varepsilon _i\geq n_i -1$$, but this forces $$k=1$$) and thus connected. Since there must exists vertices $$u$$ and $$v$$ in different parts of partition which are not connected, there exists a path between them which lenght is clearly at least $$3$$ and we are done.
• Ah, nice! I should have dug deeper. – Calvin Lin Jul 9 at 19:53