In a nearest neighbors graph (with odd number of vertices) is it possible that no vertex has degree one? [closed]

Solution 1:

With your clarification, it is a famous puzzle to prove the answer to your question is "no." This can be proven by induction as follows. I will imagine all of these edges as directed, so $x\longrightarrow y$ means that $y$ is $x$'s nearest neighbor.

The base case $p=3$ is easy enough; the vertex opposite the shortest edge of the triangle will have degree $1$.

When $p\ge 5$, consider two vertices $x$ and $y$ which are closest to each other. Let $S$ be the set of all vertices except $x$ and $y$. There are two cases:

• Suppose there exists a vertex $z\in S$ whose nearest neighbor is $x$ or $y$. In that case, there are at most $p-3$ vertices in $S$ that are pointed to, since none of $x,y,$ or $z$ points to any vertex in $S$. Since $|S|=p-2$, this means some vertex in $S$ is not pointed to, so that vertex has degree $1$.

• Otherwise, every vertex in $S$ points to another vertex in $S$. This is a smaller version of the original problem, to which we can apply the induction hypothesis to conclude some vertex in $S$ has degree at most $1$.