THEOREM 3, p. 51 — a finite graph is a subtree graph if and only if it is chordal
ProvedGavrilSubtree.Chordal.theorem_3Let be a finite simple graph. Then is the intersection graph of a family of subtrees of a tree if and only if is chordal, i.e. every simple circuit of with more than three vertices has an edge connecting two non-consecutive vertices of the circuit:
This is the main theorem of Gavril's paper. It characterizes chordal graphs geometrically, generalizing interval graphs (intersection graphs of intervals of a line, the subtree graphs of a path), and underlies the clique-tree representation used for chordal graphs in sparse matrix elimination, database theory and graphical models.
Formalization Note Trees are combinatorial trees and subtrees are nonempty vertex sets inducing connected subgraphs (see the definitions file; this gives the same class of graphs as the paper's topological subtrees). Chordality is the cycle–chord definition, not a perfect-elimination ordering. is finite, as in the paper, and may be empty.
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
namespace GavrilSubtree.Chordal
universe u
theorem theorem_3 {V : Type u} [Fintype V] (G : SimpleGraph V) :
IsSubtreeGraph G ↔ IsChordal G := by sorry
end GavrilSubtree.Chordal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.