2
$\begingroup$

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

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

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.


| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't understand one tiny part ,why is $P=H \cup V$ ? $\endgroup$ – Yes it's me Jun 13 at 14:46
  • 1
    $\begingroup$ @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. $\endgroup$ – bof Jun 13 at 14:51
  • $\begingroup$ Ah, nice observation of "each edge has an endpoint of degree 1". $\endgroup$ – Calvin Lin Jun 13 at 20:38
2
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, nice! I should have dug deeper. $\endgroup$ – Calvin Lin Jul 9 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.