Dirac–Rose, §1, p. 48 (cited) — every nonempty finite chordal graph has a simplicial vertex
ProvedGavrilSubtree.Chordal.exists_isSimplicialchordal-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplicial-vertex
Let be a finite chordal graph with at least one vertex. Then has a simplicial vertex: a vertex whose set of neighbours is completely connected,
The paper cites this theorem of Dirac and Rose (references [14], [15]) in its introduction and uses it in the inductive step of the proof of Theorem 3.
Formalization Note The hypothesis that is nonempty is added: the statement "has a vertex" presupposes one, and it fails for the empty graph. The paper applies the theorem to a connected graph that is not complete, which is nonempty.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem exists_isSimplicial {V : Type u} [Fintype V] [Nonempty V] (G : SimpleGraph V)
(hG : IsChordal G) : ∃ v, IsSimplicial G 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. 48, §1 (theorem of Dirac [14] and Rose [15], cited)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.