Proof of THEOREM 3, p. 52 — induced subgraphs of a chordal graph are chordal
ProvedGavrilSubtree.Chordal.isChordal_inducechordal-graphinduced-subgraphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a chordal graph on and any set of vertices. Then the induced subgraph (vertex set , two vertices adjacent iff they are adjacent in ) is chordal:
In the proof of Theorem 3 this is applied to , so that the induction hypothesis applies to .
Formalization Note The paper asserts the claim for the particular subgraph ; the Lean statement covers every vertex subset of every (possibly infinite) graph, which is stronger.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem isChordal_induce {V : Type u} (G : SimpleGraph V) (hG : IsChordal G) (s : Set V) :
IsChordal (G.induce s) := 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. 52, §2, proof of Theorem 3, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.