Decomposability into two triangular forests is inherited by pullbacks along injections.
ProvedTriangularForest.DecomposesIntoTwo.comapaether-cataloglogic
Decomposability into two triangular forests is inherited by pullbacks along injections.
theorem TriangularForest.DecomposesIntoTwo.comap{H : SimpleGraph W} (f : W ↪ V) (hG : DecomposesIntoTwo G)
(hH : H ≤ G.comap f) : DecomposesIntoTwo H := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/TriangularForest/CliqueObstruction.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Logic/TriangularForest/CliqueObstruction.lean
import Mathlib
import Definitions.Def_Logic_TriangularForest_ClassProperties
import Definitions.Def_Logic_TriangularForest_Decomposition
/-!
# A clique obstruction to decomposing into two triangular forests
The sharp threshold `Kₙ` (decomposable iff `n ≤ 5`) upgrades to an obstruction for *arbitrary*
graphs: since the property of decomposing into two triangular forests is inherited by subgraphs
(pulled back along injections), any graph containing six mutually adjacent vertices fails to
decompose.
* `TriangularForest.IsTriangularForest.comap` — triangular forests pull back along injections;
* `TriangularForest.DecomposesIntoTwo.comap` — so does decomposability, whenever the pullback
of the ambient graph is the graph we decompose;
* `TriangularForest.not_decomposesIntoTwo_of_six_clique` — a graph with a `K₆` subgraph does not
decompose into two triangular forests.
-/
open TriangularForest
open SimpleGraph Finset
variable {V W : Type*} {G : SimpleGraph V}Formal statement
theorem TriangularForest.DecomposesIntoTwo.comap{H : SimpleGraph W} (f : W ↪ V) (hG : DecomposesIntoTwo G)
(hH : H ≤ G.comap f) : DecomposesIntoTwo H := by sorrySource