The good-triangle certificate #
A triangle sends deg x + deg y + deg z - 6 edges to its complement. The
usual weighted cut vector therefore certifies algebraic connectivity at most
two whenever that boundary satisfies the corresponding cut inequality.
theorem
ACMax.algConn_le_two_of_good_triangle
{n : ℕ}
[Nonempty (Fin n)]
(hn : 4 ≤ n)
(G : SimpleGraph (Fin n))
(x y z : Fin n)
(hxy : G.Adj x y)
(hyz : G.Adj y z)
(hxz : G.Adj x z)
(hcut : n * (G.degree x + G.degree y + G.degree z - 6) ≤ 2 * (3 * (n - 3)))
:
A triangle satisfying the exact weighted-cut arithmetic forces
algConn G ≤ 2.