§2, proof of Lemma 1, p. 50 — subtrees each containing two of three points have a common point
ProvedGavrilSubtree.Chordal.three_point_inter_nonemptyLet be a tree, let be three vertices of , and let be any family of subtrees of (nonempty vertex sets inducing connected subgraphs) such that every contains at least two of the three points . Then the subtrees have a common point:
This is the remark with which Gavril opens the proof of Lemma 1: the three simple paths between the pairs of points meet, and each subtree contains the path between the two points it contains. It is the base of the Helly-type property of subtrees used in Lemma 1.
Formalization Note The paper takes a subset of the (finite) representing family ; the Lean statement allows an arbitrary index type , which is a stronger statement and still true. For empty the intersection is the whole tree, which is nonempty.
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
namespace GavrilSubtree.Chordal
universe u
theorem three_point_inter_nonempty {β : Type u} (T : SimpleGraph β) (hT : T.IsTree)
{ι : Type*} (t : ι → Set β) (ht : ∀ i, (T.induce (t i)).Connected) (a₁ a₂ a₃ : β)
(h : ∀ i, (a₁ ∈ t i ∧ a₂ ∈ t i) ∨ (a₁ ∈ t i ∧ a₃ ∈ t i) ∨ (a₂ ∈ t i ∧ a₃ ∈ t i)) :
(⋂ i, t i).Nonempty := by sorry
end GavrilSubtree.Chordal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.