Windmill criterion.
ProvedTriangularForest.isTriangularForest_of_unique_far_neighbouraether-cataloglogic
Windmill criterion. If every vertex other than x has at most one neighbour different
from x, then G is a triangular forest: a cycle avoiding x would have a vertex with two
distinct neighbours off x, and a cycle through x must return to x after two steps.
theorem TriangularForest.isTriangularForest_of_unique_far_neighbour(x : V)
(h : ∀ a b c : V, a ≠ x → b ≠ x → c ≠ x → G.Adj a b → G.Adj a c → b = c) :
IsTriangularForest G := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/TriangularForest/Extremal.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/Extremal.lean
import Mathlib
import Definitions.Def_Logic_TriangularForest_Complexity
import Definitions.Def_Logic_TriangularForest_Defs
import Definitions.Def_Logic_TriangularForest_Extremal
/-!
# The sparsity bound is attained for every odd order
`TriangularForest.two_mul_card_edgeFinset_le` says that a triangular forest on `n ≥ 1` vertices
satisfies `2e ≤ 3(n-1)`. Here we show that this is *sharp for every odd `n`*, by exhibiting the
friendship (windmill) graphs `Fₖ`: `k` triangles glued at a common centre.
* `TriangularForest.isTriangularForest_of_unique_far_neighbour` — a structural membership
criterion: if every vertex other than a fixed vertex `x` has at most one neighbour besides
`x`, then the graph is a triangular forest. This is the "windmill" criterion, and it is proved
by a rotation argument on cycles rather than by a finite check;
* `TriangularForest.fan` — the friendship graph `Fₖ` on `2k+1` vertices;
* `TriangularForest.isTriangularForest_fan` — `Fₖ` is a triangular forest;
* `TriangularForest.card_edgeFinset_fan` — `Fₖ` has exactly `3k` edges;
* `TriangularForest.sparsity_bound_attained` — hence `2e = 3(n-1)` for `n = 2k+1`: the bound of
`two_mul_card_edgeFinset_le` cannot be improved for any odd order.
-/
open TriangularForest
open SimpleGraph Finset
variable {V : Type*} {G : SimpleGraph V}Formal statement
theorem TriangularForest.isTriangularForest_of_unique_far_neighbour(x : V)
(h : ∀ a b c : V, a ≠ x → b ≠ x → c ≠ x → G.Adj a b → G.Adj a c → b = c) :
IsTriangularForest G := by sorrySource