Proof of THEOREM 3 (first half), p. 51 — every subtree graph is chordal
ProvedGavrilSubtree.Chordal.isChordal_of_isSubtreeGraphchordal-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subtree-graph
Every subtree graph is chordal: if is the intersection graph of a family of subtrees of a tree, then every simple circuit of with more than three vertices has an edge joining two non-consecutive vertices of the circuit.
This is the "only if" half of the main theorem (Theorem 3). A chordless circuit of length at least four in would produce a circuit in the tree.
Formalization Note The vertex set is not assumed finite; the statement holds for arbitrary graphs, which is stronger than the paper's finite setting.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem isChordal_of_isSubtreeGraph {V : Type u} (G : SimpleGraph V)
(hG : IsSubtreeGraph G) : IsChordal 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), p. 51, §2, proof of Theorem 3, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.