Can lines connecting nearest neighbors ever cross? I don't have any background in graph theory so I am sorry if this is a basic question.  I want to know if lines connecting nearest neighbors can cross in a few different cases.  


*

*I have convinced myself that if there are no ties for nearest
neighbor it is impossible for lines to cross.  Is this correct?

*I think it might still be impossible even if ties are allowed, in which case either or both lines can be drawn but I haven't come up with solid reasoning to back that up.

*This case is a bit more complicated.  Say that points can be connected to their second nearest neighbor if a line originating from them has yet to be drawn and they are already connected to their nearest neighbor.  In this condition, two pairs of points very far from one another would be connected into one long line.  Each pair would get a line connecting it to its nearest neighbor and then one or two lines would connect between the pairs.  Connecting to the third nearest neighbor is not allowed.  It seems to me that in this case as well no lines would cross.


I have no idea where to begin looking for formal math to back up these statements.  Is there a general theory of lines crossing in a network of nearest neighbor connections?  Any help would be appreciated.

Assume $A,B,C,D$ are distinct points, $B$ is the closest to $A$ of $B,C,D$, and $D$ is the closest to $C$ of $A,B,D$ (with possible ties).  Suppose the lines $AB$ and $CD$ cross at $E$.  If $E$ is $A$ or $B$, it is closer to $C$ than $D$ is, contradicting the assumption that $D$ is the closest to $C$.  Similarly if $E$ is $C$ or $D$, it is closer to $A$ than $B$ is.   The remaining case is where $E$ is distinct from $A,B,C,D$.  Then $d(A,D) < d(A,E) + d(E,D)$ and $d(B,C) < d(B,E) + d(E,C)$ so 
$d(A,D) + d(B,C) < d(A,E)+d(E,B) + d(C,E)+d(E,D) = d(A,B)+d(C,D)$.  But by assumption
$d(A,B) \le d(A,D)$ and $d(C,D) \le d(B,C)$ so $d(A,B) + d(C,D) \le d(A,D)+d(B,C)$, contradiction.
