Ponder This Challenge - March 2025 - Electric networks in graphs

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\ldots 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

Where the implicit assumption is that the vertices $1,2,\ldots ,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,\ldots,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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  March 2025 Solution:

  The minimal solution for n=10 is 15 edges (using an additional node):

  [(9, 10), (1, 11), (5, 8), (6, 9), (7, 10), (8, 10), (1, 4), (2, 11), (6, 7), (4, 5), (8, 9), (3, 6), (2, 5), (11, 3), (4, 7)]

  For n=12 the minimal solution is 18 edges. A nonplanar solution:

  [(1, 13), (10, 11), (5, 8), (6, 9), (9, 12), (1, 4), (7, 11), (2, 13), (7, 9), (4, 5), (8, 12), (6, 10), (10, 12), (3, 6), (2, 5), (3,13), (4, 7), (8, 11)]

  An easy way to compute resistances for a given graph is to compute it's Laplacian matrix $L$, compute its pseudo-inverse $L^+$ and use the formula $R_{u,v} = L^+_{u,u}+L^+_{v,v}-2L^+_{u,v}$

  The solver Li Li suggested a nice way to determine the minimum edge count, and to search for solutions:

  "First we observe that each vertex from 1 to n must have at least degree 2, and they cannot be connected to exactly 2 vertices from 1 to n (otherwise it would have equal effective resistance to these two vertices), so it either has at least three edges connected to vertices from 1 to n, or at least one edge connected to an additional vertex (outside 1 to n) and an edge connected to another vertex from 1 to n. Either case it contributes to 1.5 edge to the total number of edge. So the total number of edge must be at least 1.5n.

  To find a solution with exactly 1.5n edges, we start from 3 regular graphs for n = 10 and 12 (there are 19 and 85 respectively) and consider adding one additional vertex and connecting it to some existing vertices (of course removing some of the existing edges). We see that the existing edges removed must be a cycle. So we just try for each simple cycle, remove it and connect each vertex to the additional vertex. Fortunately we found the required number of solutions (didn’t consider multi edge graph case or at least two additional vertices)."

Solvers

• Avi Levin (2/3/2025 9:33 PM IDT)
• *King Pig (3/3/2025 4:06 AM IDT)
• Alper Halbutogullari (4/3/2025 10:47 AM IDT)
• *Lazar Ilic (4/3/2025 11:17 AM IDT)
• *Daniel Bitin (4/3/2025 5:45 PM IDT)
• *Sanandan Swaminathan (5/3/2025 6:49 AM IDT)
• *Bert Dobbelaere (5/3/2025 9:34 AM IDT)
• Juergen Koehl (5/3/2025 2:37 PM IDT)
• Gary M. Gerken (5/3/2025 4:09 PM IDT)
• *Bertram Felgenhauer (5/3/2025 9:09 PM IDT)
• Shirish Chinchalkar (6/3/2025 5:21 PM IDT)
• *Dan Dima (12/3/2025 2:50 PM IDT)
• *Klaus Nagel (16/3/2025 12:18 AM IDT)
• Ruben Menendez (18/3/2025 10:40 AM IDT)
• *Latchezar Christov (18/3/2025 10:47 AM IDT)
• *Yi Jiang (18/3/2025 1:26 PM IDT)
• Dieter Beckerle (19/3/2025 1:16 PM IDT)
• Lorenz Reichel (22/3/2025 10:19 AM IDT)
• Shouky Dan & Tamir Ganor (24/3/2025 8:16 AM IDT)
• Kang Jin Cho (27/3/2025 9:16 AM IDT)
• Reiner Martin (27/3/2025 4:04 PM IDT)
• Nyles Heise (29/3/2025 5:39 AM IDT)
• Paul Lupascu (30/3/2025 8:38 PM IDT)
• *Matt Rearick (30/3/2025 10:16 PM IDT)
• *David Greer (31/3/2025 1:20 PM IDT)
• Franciraldo Cavalcante (31/3/2025 11:46 PM IDT)
• Radu-Alexandru Todor (1/4/2025 3:12 AM IDT)
• Karl Mahlburg (1/4/2025 4:17 AM IDT)
• *Li Li (5/4/2025 6:46 AM IDT)
• David F.H. Dunkley (5/4/2025 5:10 PM IDT)
• Daniel Chong Jyh Tar (6/4/2025 12:31 PM IDT)
• Marco Bellocchi (9/4/2025 1:22 AM IDT)