Proof of Proposition 3.4, p. 407 — a graph with k nodes and no cycles has at most k − 1 edges
ProvedCompOT.Vertices.prop_3_4_forest_edge_boundacyclic-graphforestgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a simple graph on a finite set of vertices. If has no cycles (it is a forest), then
This is the counting step that turns the acyclicity of the support graph into the bound of nonzero entries.
Formalization Note is natural-number subtraction; for it reads , which is correct since the empty graph has no edges. The number of edges is Nat.card G.edgeSet.
Preamble
import Mathlib
Formal statement
namespace CompOT.Vertices
/-- End of the proof of Proposition 3.4, p. 407: a graph with `k` nodes and no cycles has at
most `k − 1` edges. Stated for a simple graph on a finite vertex type; `k − 1` is natural
subtraction, which for `k = 0` reads `0` (the empty graph has no edges). -/
theorem prop_3_4_forest_edge_bound {V : Type*} [Finite V] (G : SimpleGraph V)
(hG : G.IsAcyclic) :
Nat.card G.edgeSet ≤ Nat.card V - 1 := by sorry
end CompOT.Vertices
Source
Peyré & Cuturi, Computational Optimal Transport (FnT ML 2019), §3.4.1, end of the proof of Proposition 3.4, p. 407
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.