Triangle Inequality in Random Edge-Weighted Graphs

Setup

For each integer \( N \) from 3 to 10, construct a fully connected undirected graph (a complete graph \( K_N \)). Each edge is assigned a weight drawn uniformly at random from the interval [0.1, \ln N].

There are \( \binom{N}{3} \) triangles in each graph. For each triangle, we check whether the triangle inequality holds. That is, for any triangle with edge lengths \( a, b, c \), the triangle inequality is satisfied if:

\[ \begin{aligned} a + b &> c \\\\ a + c &> b \\\\ b + c &> a \end{aligned} \]

Equivalently, the triangle is valid if the longest side is less than the sum of the other two.

Goal

Generate 100 random graphs for each \( N \in \{3, 4, \dots, 10\} \)
Sample all edge weights from \( \text{Uniform}(0.1, \ln N) \)
Check all triangles to see if the triangle inequality is satisfied
Estimate:
- The probability that all triangles in a graph are valid
- The average fraction of valid triangles per graph

Analytical Insight

The triangle inequality fails when one side becomes too large relative to the other two. As \( \ln N \) increases, the range of edge lengths expands, increasing the chance of such imbalance.

We expect as \( N \) increases:

The variance of edge lengths increases
More unbalanced triangles are likely to form
Probability that all triangles are valid will decrease

Known Result (Reference)

For three side lengths sampled from \( \text{Uniform}(0,1) \), the triangle inequality holds with probability:

\[ P = \frac{1}{4} \]

For general ranges \( [a, b] \), the region satisfying the inequality is a sub-volume of the cube \( [a,b]^3 \):

\[ P(N) = \frac{1}{(\ln N - 0.1)^3} \int_{0.1}^{\ln N} \int_{0.1}^{\ln N} \int_{0.1}^{\ln N} \mathbf{1}_{a + b > c \land a + c > b \land b + c > a} \, da\, db\, dc \]

This is hard to solve analytically, but we can estimate it through simulation.

Next Step

We will simulate this behavior and plot:

The average probability that a triangle in the graph is valid
The probability that all triangles in a graph are valid

How Many Samples Do We Need?

To estimate the probability that the triangle inequality holds (either for individual triangles or entire graphs), we use a Monte Carlo simulation: we sample random graphs many times and count how often the inequality holds.

The number of samples needed depends on how precise we want our estimate. Assuming we want a 95% confidence interval with a ±1% margin of error for the probability \( p \), the number of samples required is approximately:

\[ n \approx \frac{1.96^2 \cdot p(1 - p)}{\epsilon^2} \]

For a conservative estimate (assuming \( p \approx 0.5 \)), this simplifies to:

\[ n \approx \frac{0.96}{\epsilon^2} = \frac{0.96}{0.0001} = 9600 \text{ triangle samples} \]

Since each complete graph \( K_N \) contains \( \binom{N}{3} \) triangles, we can divide this target sample size by the number of triangles per graph to determine how many graphs to simulate:

N	Triangles per Graph	Graphs Needed (approx.)
3	1	9600
4	4	2400
5	10	960
6	20	480
7	35	274
8	56	172
9	84	115
10	120	80

These values represent the number of runs needed to estimate the probability that a random triangle is valid with a 1% margin of error. Estimating whether all triangles in a graph are valid is a stricter condition and more binary (pass/fail per graph), so we will still aim for at least 100–1000 runs per \( N \), depending on available compute time.

In the upcoming Monte Carlo simulation, we’ll:

Generate many random graphs for each \( N \in \{3 \dots 10\} \)
Count how many triangles satisfy the inequality
Estimate both:
- The average fraction of valid triangles per graph
- The probability that all triangles in a graph are valid

This will give us a computational estimate of how triangle inequality behaves in edge-weighted graphs as a function of the number of nodes and the distribution of edge weights.

Simulation Setup

We explore how likely it is for all triangles in a randomly weighted complete graph \( K_N \) to satisfy the triangle inequality. For each \( N \) from 3 to 10:

A fully connected undirected graph is constructed with \( N \) nodes.
Each edge receives a weight sampled uniformly from \([0.1, \ln N]\).
All triangles (i.e. all \( \binom{N}{3} \) node triplets) are tested against the triangle inequality condition: \[ a + b > c,\quad a + c > b,\quad b + c > a \]

For each \( N \), a number of random graphs are generated (ranging from 1,000 to 10,000 depending on \( N \)), and we compute the fraction of those graphs in which every triangle is valid.

The simulation results are presented as a line chart on a separate page: View Simulation Results

Prepared by Stephen Guerin — • April 2025