BUMP BUMP BUMP!

The following approach helps. Use Delaunay triangulation to obtain a triangulation with a very special properties - the circumcircle of each triangle contains no other points among the given ones except its three vertices. Next, choose an edge of each triangle - one edge per triangle. Each of the circles can cover only one edge (pair) and eventually a vertex from another pair. Then slightly move each circle appropriately.

These kind of problems seems easy but really tricky, and the solution is surprisingly short. The idea is like another famous problem: Quote: There are $2n$ points on the plane. No three of them lie on the same straight line. Prove that it is possible to split these points into $n$ pairs that the line segments connecting each pair of points do not intersect. There are many proof to this problem. The shortest proof is find the pair $A_iB_i$ such that $\sum|A_iB_i|$ takes minimum value. Now if $A_iB_i$ and $A_jB_j$ intersect at point $P,$ then $$|A_iB_j|+|A_jB_i|<(|A_iP|+|B_jP|)+(|A_jP|+|B_iP|)=|A_iB_i|+|A_jB_j|,$$contradiction! Back to this problem, we also need to find a function that takes minimum value. Here we take $\sum |A_iB_i|^2.$ Now we take the circles with diameter $A_iB_i.$ Now note that any two segments don't intersect, otherwise if $A_iB_i$ and $A_jB_j$ intersect at $P$ and WLOG $\angle A_iPA_j\le 90^{\circ},$ then $$|A_iB_i|^2+|A_jB_j|^2>(|A_iP|^2+|B_iP|^2)+(|A_jP|^2+|B_jP|^2)=(|A_iP|^2+|A_jP|^2)+(|B_iP|^2+|B_jP|^2)\ge |A_iA_j|^2+|B_iB_j|^2,$$contradiction! Now if a point was in the circle with diameter $A_iB_i,$ call the point $A_j.$ If $B_j$ is also inside the circle, they must be in the same semicircle as segments don't intersect. WLOG let $A_iA_jB_jB_i$ be the convex quadrilateral, now we prove $|A_iB_i|^2+|A_jB_j|^2>|A_iA_j|^2+|B_iB_j|^2$ to get contradiction. Let $B_iA_j$ intersect the circle at another point $T,$ then $|A_iB_i|^2-|A_iA_j|^2=|B_iT|^2-|A_jT|^2=|B_iA_j|\cdot (|B_iA_j|+2|A_jT|)>|A_jB_i|^2.$ Let $B_jH\perp A_jB_i$ at $H.$ then $|B_iB_j|^2-|A_jB_j|^2=|B_iH|^2-|A_jH|^2<|A_jB_i|^2.$ Therefore $|A_iB_i|^2+|A_jB_j|^2>|A_iA_j|^2+|B_iB_j|^2.$ If $B_j$ is out of the circle, note that the above proof still work when $A_iA_jB_jB_i$ be the convex quadrilateral, so here we consider $A_iB_jA_jB_i$ is the convex quadrilateral. (if $\triangle A_iB_jB_i$ is the convex hull it is the same). Although the graph is not same, but the idea is still similar. Still we prove $|A_iB_i|^2+|A_jB_j|^2>|A_iA_j|^2+|B_iB_j|^2.$ Let $A_iH_1\perp B_iB_j$ and $A_jH_2\perp B_iB_j$ at $H_1,H_2.$ Now $|A_iB_i|^2-|A_iB_j|^2=|B_iH_1|^2-|B_jH|^2=|B_iB_j|\cdot (|B_iH_1|-|B_jH_1|),$ and $|A_jB_j|^2-|A_jB_i|^2=|B_iB_j|\cdot (|B_jH_2|-|B_iH_1|).$ Add them up and because $|H_1H_2|>0$ we are done. This ends the proof.$\Box$

EthanWYX2009 wrote: Now we take the circles with diameter $A_iB_i.$ It doesn't work. You can take, for example, an equilateral triangle and its centre.

dgrozev wrote: The following approach helps. Use Delaunay triangulation to obtain a triangulation with a very special properties - the circumcircle of each triangle contains no other points among the given ones except its three vertices. Next, choose an edge of each triangle - one edge per triangle.

However we can easily repair dgrozev's argument as follows (I assume that he meant this too). Note that the following claim is valid: Proposition. For any set of \(2n\) points on the plane consider their arbitrary triangulation. Then we can couple these \(2n\) points so that each pair corresponds to an edge in the triangulation. Proof. Induct on \(n\). The base \(n=1\) is obvious. For the step consider any edge of the triangulation on its border. Choose its vertices as one of our couples and remove the edges coming out of them. Then we are left with \(2n-2\) points and their valid triangulation. Thus we can couple them according to the hypothesis.$\square$ Now I think everything works fine.

>For any set of \(2n\) points on the plane consider their arbitrary triangulation. Then we can couple these \(2n\) >points so that each pair corresponds to an edge in the triangulation. That's wrong. The counterexample is a solution to the problem https://artofproblemsolving.com/community/c6h3325053p30765294 The statement is true precisely for Delaunay triangulation, but it is hard to prove.

a_507_bc wrote: There are $2n$ points on the plane, no three of which lie on the same line. Some segments are drawn between them so that they do not intersect at internal points and any segment with ends among the given points intersects some of the drawn segments at an internal point. Is it true that it is always possible to choose $n$ drawn segments having no common ends? This is the problem under your url, @fagot, and the red part is completely self-contradictory. Maybe in the red sentence the first word "internal" should be replaced by "external"? If this replacement is to be made, then according to the condition there will be segments intersecting in internal points so I do not see how this is related to any triangulation at all. Anyway the problem you showed us is ill-formulated. So could you please provide an explicit counterexample to my proposition or point out a logical flaw in its proof (if any)?

Indeed, I was sloppy in #5. Fortunately, it can be fixed due to the fact that any Delaunay triangulation of even number of vertices has a perfect matching - a non easy result proved by Dillencourt. kiyoras_2001 wrote: Proposition. For any set of \(2n\) points on the plane consider their arbitrary triangulation. Then we can couple these \(2n\) points so that each pair corresponds to an edge in the triangulation. Proof. Induct on \(n\). The base \(n=1\) is obvious. For the step consider any edge of the triangulation on its border. Choose its vertices as one of our couples and remove the edges coming out of them. Then we are left with \(2n-2\) points and their valid triangulation. Thus we can couple them according to the hypothesis.$\square$ This is not true for any triangulation. The problem with your proof is that after removing the vertices, it may not be a triangulation any more, and the graph may be split in several components.

Oh, now I see the problem in my argument, thanks for pointing it out. So my "proof" is incorrect. However it still does not assert the incorrectness of my proposition. Are there any explicit counterexamples? Thanks.