Pares de puntos exactamente $1$ unidad aparte en el plano

Question

Este es un problema que encontré en un texto de teoría de grafos, pero no puedo resolverlo.

Dejemos que $S$ sea un conjunto de $n$ puntos en un plano, cuya distancia entre dos cualesquiera es al menos uno. Demuestre que hay a lo sumo $3n$ pares de puntos de $S$ a la distancia exacta de uno.

Experimentando, pensé que la forma de conseguir el mayor número de puntos de distancia exactamente 1 sería colocar los puntos en una cuadrícula hecha de triángulos equiláteros. Al construir esta cuadrícula, parece que al añadir un nuevo vértice, puedo conectarlo a otros 2 o 3 puntos para tener la distancia exactamente 1, lo que implica que sólo puedo añadir como máximo 3 nuevos pares de puntos separados 1 unidad por cada punto que añada, lo que sugiere el resultado. ¿Existe una forma no manual de mostrar esto?

Answer 1

Cada punto puede tener como máximo $6$ vecinos a distancia $1$ por lo que puede estar como máximo en $6$ pares. Cada par contiene $2$ puntos. Por lo tanto, puede haber como máximo $6n/2=3n$ tales pares.

Answer 2

Es natural (sobre todo porque este es un texto de teoría de grafos...) convertir el conjunto $S$ en un gráfico conectando dos puntos (vértices) si están exactamente a una unidad de distancia. ¿Qué puedes decir de este gráfico? ¿Puedes decir algo sobre los grados de los vértices? ¿Qué intentas demostrar con este gráfico?