# Average edge-cost optimality of minimum spanning trees

Are there counter examples to the conjecture, that in a complete, finite and symmetric weighted graph $$G\left(V,E,\omega\right),\ E=\lbrace \lbrace i,j\rbrace\subset V\times V\rbrace,\ \omega:E\ni e\mapsto\mathbb{R_0^+}$$ the edges constituting to the solution of $$\min\frac{\sum_{i,j} \alpha_{ij}\omega(e_{ij})}{\sum_{i,j} \alpha_{ij}}$$ $$\sum_{i\ne u}\alpha_{iu}=0,\quad \sum_{i\ne u}\alpha_{ui}=1$$ $$\sum_{j\ne v}\alpha_{jv}=1,\quad \sum_{j\ne v}\alpha_{vj}=0$$ $$\sum_{i\notin\lbrace j,k,u,v\rbrace}\alpha_{ik}\ -\sum_{j\notin\lbrace i,k,u,v\rbrace}\alpha_{kj}=\ 0$$ $$\alpha_{ij}\in\lbrace 0,1\rbrace$$

i.e. to the path connecting $$u$$ to $$v$$ with minimal average edge-weight are elements of the set of edges constituting to the minimum spanning tree (MST)?

Edit to further explain, as requested by Brendan McKay:

• the graphs, that this question relates to, are undirected and shall have no cycles of negative length; it is further required, that the graph is connected and if not, the question relates to the connected components.

• a simple path connecting two distinct vertices $$u$$ and $$v$$ in such a graph is characterized

• by the set $$P_{uv}$$ of edges constituting to that connecting simple path,
• by the cardinality $$C_{uv}$$ of that set of edges.
• by the sum of weights $$L_{uv}$$ of $$P_{uv}$$, i.e. the path's length

• the average edge-length of $$P_{uv}$$ is then defined as $$\frac{L_{uv}}{C_{uv}}$$.
This must not be confused with the average path-length, which is also a the subject of research!

for explaining, what is conjectured, further notation is introduced:

$$P_{uv}^E$$, $$L_{uv}^E$$ and $$C_{uv}^E$$ shall be the set of edges, its sum of weights and its cardinality of a path between $$u$$ and $$v$$ consisting of edges from the entire edge-set $$E$$ of $$G$$, whereas for $$P_{uv}^{\mathrm{MST}}$$, $$L_{uv}^{\mathrm{MST}}$$ and $$C_{uv}^{\mathrm{MST}}$$ the set of edges shall be restricted to $$G$$'s minimum spanning tree MST.

Conjecture: $$\frac{L_{uv}^{\mathrm{MST}}}{C_{uv}^{\mathrm{MST}}}\ \le\ \frac{L_{uv}^E}{C_{uv}^E}\ \forall u,v\in G$$

• Please explain better. What are the conditions and what is the (conjectured?) conclusion? Mar 25, 2018 at 0:25

Meanwhile I found a simple counterexample: the least average edge-length of a path from node A to node D would be A$\mapsto$B$\mapsto$C$\mapsto$D with an average edge length of $\frac{1+1+2}{3}=\frac{4}{3}$, whereas in the MST (bold lines) the only path from A to D is A$\mapsto$D with a length of $\frac{2}{1}=2$