# Average Edge-cost Optimality of MSTs

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 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}^{MST}$, $L_{uv}^{MST}$ and $C_{uv}^{MST}$ the set of edges shall be restricted to $G$'s minimum spanning tree MST.

Conjecture: $$\frac{L_{uv}^{MST}}{C_{uv}^{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? – Brendan McKay Mar 25 '18 at 0:25

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$