LEMMA 1, p. 50 — for every completely connected set A of a subtree graph, ⋂_{v∈A} v̄ ≠ ∅
ProvedGavrilSubtree.Chordal.lemma_1Let be a graph represented by a family of subtrees of a tree (distinct vertices are adjacent exactly when their subtrees intersect). Then for every finite completely connected set of (a finite set of pairwise adjacent vertices)
This is the Helly property of subtrees of a tree: pairwise intersecting subtrees have a common point. It is what lets Theorem 2 attach to each clique a point of the tree.
Formalization Note The paper's graphs are finite, so every completely connected set is finite; the Lean statement takes as a Finset and does not assume finite. Finiteness of is necessary: infinitely many nested rays of an infinite tree pairwise intersect with empty intersection. For the intersection is the whole tree, which is nonempty.
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
namespace GavrilSubtree.Chordal
universe u
theorem lemma_1 {V : Type u} {G : SimpleGraph V} {β : Type u} {T : SimpleGraph β}
{F : V → Set β} (hF : IsSubtreeRep G T F) (A : Finset V) (hA : G.IsClique (A : Set V)) :
(⋂ v ∈ A, F v).Nonempty := by sorry
end GavrilSubtree.Chordal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.