Edge counts across label fibers
Provededge_sum_eq_of_adjacent_vertices_share_label__p2m_bea9e6a7_0ad4_4019_b431_579d8a36e318_a1approximation-algorithmsplanar-graphstreewidth
For a finite graph whose adjacent vertices always have the same label, the sum of the edge counts of the graphs induced on each label fiber equals the graph's edge count. The fibers partition vertices, and the adjacency hypothesis ensures every edge lies in exactly one fiber.
Preamble
import Mathlib set_option autoImplicit false
Formal statement
theorem edge_sum_eq_of_adjacent_vertices_share_label__p2m_bea9e6a7_0ad4_4019_b431_579d8a36e318_a1 {V ι : Type} [Fintype V] [Fintype ι] (G : SimpleGraph V) (label : V → ι) (h : ∀ ⦃u v : V⦄, G.Adj u v → label u = label v) : (Finset.univ.sum fun i : ι => (G.induce {v : V | label v = i}).edgeSet.ncard) = G.edgeSet.ncard := by sorrySource
David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011, author electronic manuscript, Section 10.2, proof of Theorem 10.11, pp. 270-272. https://doi.org/10.1017/CBO9780511921735. Bounded tree-width of the pieces: Robertson–Seymour (planar graphs of radius r have tree-width at most 3r+1) / Bodlaender (k-outerplanar graphs have tree-width at most 3k-1).