Uniquely defining a graph via edge lengths

Question

Consider a complete graph. Let $D_E$ be the set of all edges lengths (one may see it as simply the Euclidean distances between any two vertices, where I'm naturally considering straight edges). For a graph of size $n$, we have $n(n-1)/2$ such edges, thus lengths.

Apart from rotations and reflections, is the complete graph uniquely defined for any given $n$? I feel the answer should be yes, and it's relatively easy to see in small cases. But how should I argue regarding bigger values of $n$? Maybe by induction?

If yes, what is the minimum amount of straight edge lengths we need to have in order for the graph to be uniquely defined under the same considerations?

Answer 1

user21820's count of $2n-2$ lengths is indeed optimal, provided $n$ is large enough.

Consider being the one responsible for locating the vertices $\{V_i= (x_i, y_i)\}_{i=1}^n$ from the lengths given. If they are not all colinear, we can assume WLOG that $V_3$ does not lie on $\overleftrightarrow {V_1V_2}$. Since we can only identify the locations up to a rigid motion, we can arbitrarily choose these three equations to hold: $$x_1 = 0\\y_1 = 0\\y_2 = 0$$

Now there will be exactly four solutions, depending on whether $V_2$ lies on the positive or negative $x$-axis, and whether $V_3$ is in the upper or lower half-plane.

This leaves us with $2n-3$ degrees of freedom among the $x_i, y_i$ that must be determined. Each length we are given is a quadratic equation of the form $$(x_i - x_j)^2 + (y_i - y_j)^2 = d_{ij}^2$$ The equation removes 1 degree of freedom, but provides two possible values for the determined variable.

Thus it will require $2n-3$ equations (i.e., lengths) to remove all the degrees of freedom. But at that point, we can have $2^{2n-3}$ solutions (less if any of the lengths are for vertical or horizontal edges - but there will be at least some figures where other than $V_1V_2$ this does not occur). Therefore when $n$ is large enough, we get too many solutions, and at least one more more bit of information is necessary to distinguish between them. Thus in general we will need at least $2n-2$ lengths to fully specify the figure.

In special cases (low $n$ or colinear vertices) it may be possible to specify the figure with fewer lengths. A triangle requires only $3$ lengths, and a quadrilateral requires $5$. But I believe a hexagon cannot be specified with fewer than $8$ lengths.

Answer 2

For a planar complete graph with straightline edges (which, as I remarked in my comment, is just a way of describing a geometric figure), choose any 3 non-colinear vertices $A, B, C$. For every other vertex $D$, there is only one other point in the entire plane that is the same distance from $A$ and $B$ as $D$ is. However, that other point will be a different distance from $C$ than $D$.

Thus the position of every other vertex in the plane is completely determined by the length of its edges to $A, B, C$. Also the position $C$ is determined by the length of its edges to $A$ and $B$, up to reflection through the line $\overline{AB}$. And the location of $B$ is restricted to a circle about $A$. Moving the location of $B$ rotates the whole graph about $A$. Flipping the location of $C$ to the other possible point reflects the whole graph. Thus the edge distances completely determine the graph up to translation (selecting the location of $A$), rotation (selecting the location of $B$), and reflection (selecting the location of $C$).

As for the minimum number of edge lengths needed, since you just need the three lengths between $A, B, C$, and for each other vertex, the 3 edge lengths to $A, B, C$. For a graph of $n$ vertices, this is $3(n-2)$ edge lengths total. And that is a "local" minimum, because if you drop any one of those lengths, there will be a point that now has freedom to flip to the other side of $\overline{AB}$ or $\overline{AC}$ or $\overline{BC}$. By itself, this doesn't prove $3(n-2)$ cannot be reduced by switching to some completely different scheme than "distances to 3 points", but I doubt it can be.

Answer 3

Paul's answer is not optimal. The regular pentagon ABCDE is uniquely defined by the $8$ edges AB, BC, CD, DE, EA, AC, CE, BD. In general, for $n>3$ any convex $n$-gon is uniquely defined by $\color{blue}{(2n-2)}$ edges, namely the external edges plus the diagonal edges from one vertex $C$ plus one last edge between the vertices next to $C$. (You can deal with all smaller $n$ separately.)

The reason is simple. Except for the last one, these edges divide the interior of the polygon into a sequence of triangles such that each pair of adjacent triangles share a diagonal edge from $C$. Also, the total angle at $C$ is the sum of the directed angles made by the triangles at $C$, which is maximum exactly when all those angles are in the same direction, corresponding to the original convex polygon.

I am also pretty sure this is optimal, but am not sure how to prove it.