# Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $$n$$ nodes and $$m$$ edges, and we label each edge from $$1$$ to $$m$$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum of all edge labels on that path (or $$0$$ for a trivial path), and define the "distance" $$d(a, b)$$ from node $$a$$ to $$b$$ to be the minimum weight of all paths from $$a$$ to $$b$$ (or $$\infty$$ if $$b$$ is not reachable from $$a$$).

Define a triple $$a, b, c$$ of nodes to be defective if $$d(a, c) < d(a, b) < \infty$$ and $$d(b, c) < d(a, b)$$.

I have two questions:

A) What is the maximum number of defective triples possible?

B) What is the average number of defective triples if edge labels are assigned at random?

Unfortunately, I haven't been able to make much progress on either one, so I was hoping other people might have insight into the problem.

For A), here is a construction that gives $$2\binom{n}{3}$$ defective triples, which is almost best possible. Let $$D$$ be a digraph with vertex set $$[n]$$ and arcs $$(i,i+1)$$ and $$(i+1, i)$$ for all $$i \in [n-1]$$. Let the label of the arc $$(i,i+1)$$ be $$n-1+i$$, and the label of the arc $$(i+1, i)$$ be $$i$$.
For all $$i, I claim that $$(i,k,j)$$ is a defective triple. To see this, note that $$d(i,j)=n+j-2 < n+k-2=d(i,k)$$ and $$d(k,j)=k-1 < n+k-2=d(i,k)$$.
Similarly, $$(j,k,i)$$ is also a defective triple.
Thus, this example contains $$2\binom{n}{3}$$ defective triples.
In general, note that if $$(a,b,c)$$ is a defective triple, then $$(a,c,b)$$ cannot be a defective triple. Thus, every digraph on $$n$$ vertices contains at most $$3 \binom{n}{3}$$ defective triples, so our bound is tight up to a factor of $$\frac{3}{2}$$.