Per-edge triangle count controls cut size and algebraic connectivity: a local-to-global bridge via the minimum triangle cover

A central challenge in spectral graph theory is to derive global spectral propertiesof a graph from local structural constraints. We address this for thealgebraic connectivity λ2(L) and a new local invariant: the minimum peredgetriangle count τ (G) = mine∈E tri(e), where tri(e) = (A2)ij counts thetriangles containing edge e = (i, j).The main contribution is a short combinatorial lemma: if τ (G) ≥ k, thenevery non-trivial cut (S, ¯ S) satisfies |∂S| ≥ k + 1. The proof identifies, forany cut edge e = (i, j), exactly k additional distinct cut edges forced by thecommon neighbours of i and j; the distinctness follows from the absence ofself-loops. The lemma is verified exhaustively (592,464 cuts, zero violations).From this lemma, via the Cheeger isoperimetric inequality [1, 2], we derivea lower bound on algebraic connectivity:λ2(L) ≥ 2(τ (G) + 1)2 n2Δ3 ,where n is the order of G and Δ its maximum degree. This is the first lowerbound on λ2 in terms of a per-edge triangle statistic. The bound is quantitativelyweak (empirical slack ≈ 500–1300×) because the Cheeger inequalityloses a factor of h(G) in the lower direction; improving the dependence on nand Δ is formulated as an open problem.The result is situated in the Topostability framework [3], where τ (G) ≥1 corresponds to the absence of always-fragile (AF) edges. An immediatecorollary is that AF(G) = 0 is equivalent to 2-edge-connectivity, providing agraph-theoretic characterisation of a Topostability edge class.Keywords: algebraic connectivity, triangle count, local-to-global, Cheegerinequality, cut edges, Topostability, minimum triangle cover,2-edge-connectivity