IBM Ponder This #323 · March 2025

This puzzle was suggested by Hugo Pfoertner - thanks Hugo!

Given a finite, nondirected graph (allowing multiple edges between two vertices), we can think of it as an electric network where each vertex is a node, and each edge is a resistor. Assume all edges in the graph have the same resistance $R$. It is a well-known problem to compute the resistance between any two nodes in the graph.

Given $n$, we want to find a graph that has $n$ specified vertices, such that all the resistances between those vertices are distinct. Note that the graph can have additional vertices that are not part of those counted in $n$ (but still influence the resistances between vertices). As an example, consider the following graph:

In this graph, the resistances between vertices $1\dots 5$, given $R=47$, are $[19,20,31,33,35,39,40,45,46,52]$, giving $10=\frac{n(n-1)}{2}$ distinct values, as required. This graph has one additional node, and a total of 9 edges (which is non-optimal: the optimal number is 8). The graph can be described by the list

[(1, 6), (1,4), (2,5), (2,6), (3,5), (3,5), (3,6), (4,5), (4,5)]

Where the implicit assumption is that the vertices $1,2,\dots ,n$ are the ones whose resistances are measured, and the rest are additional vertices.

We impose on the graph the constraint that no vertex may be connected to only one neighbor.

Your goal: For $n=10$, find a graph with the minimal number of edges such that between nodes $1,\dots ,10$ we have 45 distinct resistances. Supply your result as a list of edges as in the above example.

A bonus "*" will be given for solving the problem for $n=12$ (66 distinct resistances), finding all 3 solutions to the problem where the graph is planar and also finding one non-planar solution.

Solution

Best opened after a real attempt

To be added.