Numbering the edges of a graph, and a lowest path problem

Question

Consider a connected graph with $n$ vertices, such that any pair of vertices are connected with at most one edge.

For each edge we wrote a positive integer and for all the edges but one this number is fixed (it can not be changed), the last edge can be changed. The changeable edge can be changed any time, you can think it as for each path you can change its number.

For each pair of vertices consider the lowest path between them, i.e. the path, such that the sum of the numbers on the edges in the path is as small as possible. (The direction doesn't matter, since the sum is the same.)

Suppose that the sum of the numbers on the edges in these $\binom{n}{2}$ pathes are all distinct and not greater than $\binom{n}{2}$.

How many possible value does $n$ have if $n<500$?

I tried to explain as understandable as possible. It is from a Russian book named Olympiad graphs. I couldn't solve it, it seems pretty difficult and it didn't contain a full solution, only a number. So the solution must be: $45$.

This theorem might help: A graph theorem

Answer 1

This is not an answer. Rather, this is an attempt at clarifying the question that is way too long for a comment. Is this a correct 'formalization' of what is being asked?

---

Given two adjacent vertices $v_0$ and $v_1$, let $e=v_0v_1 = v_1v_0$ denote the edge that joins $v_0$ and $v_1$. Given an edge $e$, let $w(e)$ be its weight.

If $v_0,v_1,\dots,v_n$ are vertices such that for each $i\in\{1,\dots,n\}$ $v_{i-1}$ is adjacent to $v_{i}$, then $p = v_0v_1\cdots v_n$ is a path. If we let $e_i = v_{i-1}v_i$, then we may also write $p =e_1e_2\cdots e_n$. For such a path $p$, let $w(p) = \sum_{i=1}^n\,w(e_i)$.

Let $G=(V,E)$ be a graph. Given two distinct vertices $u,v\in V$, let $P(u,v)$ be the set of paths joining $u$ and $v$. Let

$$P_{\min} = \{ p\in P(u,v)\,|\, u,v \in E \,\text{ are distinct and $\forall q \in P(u,v),\, w(p) \leq w(q)$}\}.$$

Given an edge $e\in E$, let $P_{\min, e}$ be the set of paths in $P_{\min}$ that contain $e$.

---

For which $n$ can we find a connected graph $G = (V,E)$ satisfying

• $|V| = n$
• any pair of distinct vertices in $V$ are connected by at most one edge
• each edge in $E$ has a positive integer weight
• there is an edge $e \in E$ and a function $f: P_{\min,e} \longrightarrow \mathbb N\setminus\{0\}$ such that $g:P_{\min}\longrightarrow \mathbb N\setminus\{0\}$ given by

$$g(p) = \left\{ \begin{array}{cccc} w(p)&&&p \in P_{\min}\setminus P_{\min,e}\\ w(p)-w(e)+f(p)&&&p \in P_{\min,e} \end{array}\right.$$

is injective no greater than $\binom{n}2$?