Lemma 10.12 (Handshaking Lemma): every graph has an even number of odd-degree nodes
ProvedSupplyChainTheory.handshakinggraph-theorytraveling-salesman
Lemma 10.12 (Handshaking Lemma). In any undirected graph, the number of odd-degree nodes is even. The sum of all degrees is twice the number of edges, so the odd degrees are even in number. This is what guarantees that the odd-degree nodes of the spanning tree in Christofides' heuristic can be perfectly matched.
Preamble
import Definitions.Def_SupplyChainTheory_tsp
Formal statement
open Classical
namespace SupplyChainTheory
theorem handshaking {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] :
Even (Finset.univ.filter (fun v => Odd (G.degree v))).card := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 433, Sect. 10.4.7, Lemma 10.12: 'Proof. Omitted; see Problem 10.8'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.