§2, p. 50 — the subtree intersections of two different cliques are disjoint
ProvedGavrilSubtree.Chordal.inter_cliques_disjointcliquep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subtree-graph
Let be a graph represented by a family of subtrees of a tree . For two different cliques (maximal completely connected sets) of ,
Together with Lemma 1 this says that the sets , , are nonempty and pairwise disjoint, so one can pick a distinct tree point for each clique; this is the first step of the proof of Theorem 2.
Formalization Note No finiteness of is assumed; the statement holds for arbitrary graphs.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem inter_cliques_disjoint {V : Type u} {G : SimpleGraph V} {β : Type u}
{T : SimpleGraph β} {F : V → Set β} (hF : IsSubtreeRep G T F) (A₁ A₂ : Cliques G)
(hne : A₁ ≠ A₂) :
(⋂ v ∈ A₁.1, F v) ∩ (⋂ v ∈ A₂.1, F v) = ∅ := by sorry
end GavrilSubtree.Chordal
Source
Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974), p. 50, §2, the sentence after the proof of Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.