0
$\begingroup$

In the Euclidean Plane and where all edges are straight lines:

Given a collection of a edge-lengths L, how can I determine if there exists a selection of vertices such that the elements of L correspond exactly to the distances between each unique pairing of vertices?


For instance, when L=[3, 4, 5] a selection of vertices (0, 0), (0, 3), and (4, 0) satisfies these properties.

However, when L=[3, 4, 8] there is no collection of vertices who's complete graph consists exactly of three edges with lengths 3, 4, and 8; since any complete graph (in the Euclidean Plane) having three edges is a triangle, and a triangle's longest edge must be less than the sum of the other two.


  • What if the vertices must have rational coordinates?
  • What if the vertices must have integer coordinates?
  • Does the collinearity (or lack thereof) of vertices matter?

UPDATE:

I read that any complete graph of n vertices is composed of exactly $ {n\choose 3} $ triangles. So, I guess I can rule out any L with an edge-length longer than or equal to the sum of the next two shorter edge-lengths?

$\endgroup$
3
  • $\begingroup$ I don't have the time right now to go looking, but the basic question here has been asked several times, if not the variations with rational/integer coordinates. $\endgroup$ Jun 3, 2023 at 21:18
  • $\begingroup$ @MishaLavrov I'm unsure about my terminology. What keywords should I be looking for? $\endgroup$
    – Brovidio
    Jun 5, 2023 at 16:20
  • $\begingroup$ Start from math.stackexchange.com/questions/4533475, which is definitely the wrong variant of this question but has links to many more, and that should give you some keywords $\endgroup$ Jun 5, 2023 at 17:18

1 Answer 1

-1
$\begingroup$

Partial answer found here: https://math.stackexchange.com/questions/3062113


Naturally, the size of L will always be a triangle number.
The number of vertices (n) in a complete graph with L.size edges is: $$ n=\frac{1+\sqrt{1+8L {\scriptsize\text{.size}}}}{2} $$

L can complete a graph of n vertices when there is an assignment of edges to vertices such that:

  1. No two edges connect the same pair of vertices.
  2. The edges of each 3-vertex cycle obey the triangle inequality.

I don't know the best way to determine if such an assignment exits.
You can brute force every combination until finding one that works, but I'm sure there's a better way.
It may warrant a post of its own.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .