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

Question

$\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$.

Answer 1

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$.)

Induction step: Proof by contradiction.
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.

---

Answer 2

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$.

Answer 3

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.