THEOREM 2, p. 51 — G is a subtree graph iff there is a tree on μ(G) in which every μ_v(G) induces a connected subgraph
ProvedGavrilSubtree.Chordal.theorem_2characterizationclique-treep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subtree-graph
Let be a finite graph on vertex set , with set of cliques and, for , the set of cliques containing . Then
The right-hand side, a clique tree, is the canonical form of a subtree representation: the tree's vertices are the cliques and the subtree of is the set of cliques containing . Theorem 2 reduces the main theorem to constructing a clique tree for every chordal graph.
Formalization Note is finite (the paper's standing assumption) but may be empty: then and both sides hold. Connectedness of includes nonemptiness, i.e. every vertex lies in a clique, which holds for finite graphs.
Preamble
import Mathlib import Definitions.Def_GavrilSubtree_Chordal_Setting
Formal statement
namespace GavrilSubtree.Chordal
universe u
theorem theorem_2 {V : Type u} [Fintype V] (G : SimpleGraph V) :
IsSubtreeGraph 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), p. 51, Theorem 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.