Proof of THEOREM 3 (second half), pp. 51–52 — every finite chordal graph has a clique tree
ProvedGavrilSubtree.Chordal.hasCliqueTree_of_isChordalchordal-graphclique-treep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite chordal graph. Then there is a tree whose vertex set is the set of cliques such that, for every vertex , the cliques containing induce a connected subtree :
Combined with Theorem 2 this gives the "if" half of the main theorem (Theorem 3).
Formalization Note is finite but may be empty.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem hasCliqueTree_of_isChordal {V : Type u} [Fintype V] (G : SimpleGraph V)
(hG : IsChordal G) : HasCliqueTree G := 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), pp. 51–52, §2, proof of Theorem 3, second and last paragraphs
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.