How to find all possible connections between immediate lattice points in a $n\times n$ square?

Question

I am not a mathematician so my terminology might be not correct, please ignore it.

I want to calculate all possible connections between immediate lattice points in a $n\times n$ square.

Here lattice points are all points $(x, y)$ that satisfies $x \in \Bbb{N}, y \in \Bbb{N}$ and $x \le n, y \le n \ (n \in \Bbb{N}, n \ge 2)$, the square is in the first quadrant and its lower left corner is the origin, and two lattice points are immediate if they can be connected without the connection passing through another lattice point.

I have thoroughly investigated cases where $n \in \{2, 3, 4\}$, and found the following:

When $n = 2$, it is this:

It is not interesting, there are $4$ points and $6$ connections, $4$ connections of length $1$ and $2$ connections of length $\sqrt{2}$, and every connection is valid: ${4 \choose 2} = \frac{4 \cdot 3}{2} = 6 $.

When $n > 2$, things get interesting. I have manually created the graphs using GeoGebra and identified different types of lattices and colored the connections accordingly for convenience.

The above picture shows when $n = 3$, there are $9$ points and ${9 \choose 2} = \frac{9 \cdot 8}{2} = 36$, however only $28$ connections are between immediate points, as $8$ connections overlap other connections.

More specifically, there are $3$ types of points, $4$ corner points, $4$ midline points and $1$ center, and connections of lengths $\{1, \sqrt{2}, \sqrt{5}\}$ with 12 connections of length 1, 8 connections of length $\sqrt{2}$ and 8 connections of length $\sqrt{5}$. Opposite points cannot be connected directly.

When $n = 4$:

There are $3$ types of points when $n = 4$, there are $4$ corners, $8$ midline points and $4$ inner points.

There are ${16 \choose 2} = \frac{16 \cdot 15}{2} = 120$ total possible connections, but only $86$ connections are valid.

In the above picture, there are $24$ connections of length $1$, $18$ of $\sqrt{2}$, $24$ of $\sqrt{5}$, $12$ of $\sqrt{10}$ and $8$ of $\sqrt{13}$.

It is easy to see corner points cannot connect to each other, points on edges can only connect to $3$ other points horizontally and vertically, while points inside the square can connect to $4$ other points horizontally and vertically.

Each red point connects to $2$ blue points on the edges that intersect at it and cannot connect to the other $2$ blue points on those $2$ edges. Each red points can connect to the other $4$ blue points that aren't colinear with it.

So each red point can form $6$ magenta connections for a total of $4 \cdot 6 = 24$ magenta connections.

Each red point can connect to $3$ green points and not the green point opposite it so there are $12$ yellow connections.

Each blue point can connect to every other blue point except the $2$ at $3$ indices offset in either direction (clockwise or counterclockwise), so there are $\frac{8 \cdot (7 - 2)}{2} = 20$ blue connections.

Each green point can connect to all $4$ blue points that aren't colinear with it but only $2$ blue points from the $4$ colinear points. So there are $4 \cdot 6 = 24$ cyan connections.

Lastly the $4$ green points can connect to each other, so there are $6$ green connections, and order $4$ contains order $2$.

For higher orders, the number of total connections blows up quickly so I couldn't do it manually, for example the number of total connections of order $5$ is ${25 \choose 2} = 300$, but I did write a simple Python program to visualize the linear combinations with all the duplicates:

import matplotlib.pyplot as plt
from itertools import combinations, product
from matplotlib.collections import LineCollection

def graph(n):
    points = list(product(range(n), repeat=2))
    segments = list(combinations(points, r=2))

    fig, ax = plt.subplots()
    ax.add_collection(LineCollection(segments))
    ax.set_axis_off()
    plt.axis('scaled')
    fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
    plt.show()

And below are pictures of orders $5$ and $6$:

As you can see, order $5$ contains order $3$ and order $6$ contains order $4$. So all odd orders are subsets of higher odd orders and even orders are subsets of higher even orders.

I found that .gbb file is .zip file renamed, so I extracted the geogebra.xml file and wrote this Python program to double-check my calculations:

from collections import Counter
from lxml import etree
from pathlib import Path

tree = etree.fromstring(Path("C:/Users/Estranger/Desktop/four/geogebra.xml").read_bytes())

points = tree.findall('.//element[@type="point"]')

coords = dict()

for point in points:
    key = point.attrib['label']
    coord = point.find('./coords')
    x = float(coord.attrib['x'])
    y = float(coord.attrib['y'])
    coords[key] = (x, y)

def dist(a, b):
    return ((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5

segments = tree.findall('.//command[@name="Segment"]/input')

lengths = Counter()

for segment in segments:
    a = coords.get(segment.attrib['a0'])
    b = coords.get(segment.attrib['a1'])
    lengths[dist(a, b)] += 1

sorted(lengths.items())

Output:

[(1.0, 24),
 (1.4142135623730951, 18),
 (2.23606797749979, 24),
 (3.1622776601683795, 12),
 (3.605551275463989, 8)]

Unfortunately this is as far as I can go, I lack the mathematical skills to analyze my findings further, I want to know, given order $n$ and two points $(x_0, y_0)$ and $(x_1, y_1)$, how to determine whether they are immediately connected or not?

Answer 1

Let's call two connections equivalent if they have the same slope, e.g., the connection between $(0,0)$ and $(1,2)$ is equivalent to the connection between $(1,0)$ and $(2,2)$ since they both have slope $2$. Note that the restriction to immediate connections implies that equivalent connections have the same length.

Let's extend the notion of equivalence to connections where the slope of one is the additive inverse of the slope of the other. So now the connection between $(1,0)$ and $(0,2)$, with slope $-2$, is also equivalent to the connections in the preceding paragraph. It is still the case that equivalent connections have the same length.

Finally, let's extend the notion of equivalence to pairs of connections where the product of the two slopes is $\pm1$. So now the connection between $(0,0)$ and $(2,1)$, with slope one-half, is equivalent to the connections in the previous paragraphs. Again, equivalent connections have the same length.

We adopt the convention $0\times\infty=1$, so the connection from $(0,0)$ to $(1,0)$ with slope zero is equivalent to the connection from $(0,0)$ to $(0,1)$ with infinite (or, if you prefer, undefined) slope.

Now every connection is equivalent to one connection of slope $a/b$ with $0\le a\le b\le n$ and $\gcd(a,b)=1$, so we may count the number of inequivalent connections by the number of such fractions $a/b$. But this is a well-studied quantity in Number Theory; it's the number of Farey fractions of order $n$, and it's the sum of the first $n$ values of the Euler totient function, $\phi(n)$. It begins $1,2,3,5,7,11,13,19,\dots$, and is tabulated, with many links and references, at https://oeis.org/A005728

Now, there's one little wrinkle here. Equivalent connections have the same length, but connections of the same length aren't necessarily equivalent. E.g., $(0,0)$ to $(4,7)$, and $(0,0)$ to $(1,8)$, both have length $\sqrt{65}$, but they aren't equivalent. So, the number of different lengths is smaller (for $n\ge8$) than the number of inequivalent connections. Unfortunately, the number of lengths is not tabulated at the OEIS.