is_diamond_free
def
A simple graph G is diamond-free if it does not contain the diamond graph as an induced subgraph.
Statement
def is_diamond_free {V : Type*} (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.32404:131
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Built on 1
- diamond_graphThe diamond graph is the simple graph on vertex type Fin 4 obtained from the complete graph ⊤ by deleting the single edge between vertex 0…
- Used by 3
- k4_claw_diamond_free_has_no_induced_k4_subdivisionEvery simple graph containing neither an induced K4, an induced claw, nor an induced diamond contains no induced subdivision of K4.
- subdivided_k33_line_graph_isk4_diamond_free_four_chromaticLet H be the graph obtained from K3,3 by subdividing one edge exactly once, and let G be its line graph. Then G has no induced subdivision…
- subdivided_k33_line_graph_no_k4_claw_diamondThe line graph of the once-subdivided K3,3 has no induced K4, claw, or diamond.
Read back from the Lean
For a type V and a simple graph G on V, is_diamond_free G is defined to hold if and only if the diamond graph diamond_graph is not contained in G as an induced subgraph (i.e., ¬ SimpleGraph.IsIndContained diamond_graph G). Here, diamond_graph is the simple graph on vertex set Fin 4 obtained from the complete graph on 4 vertices by removing the single edge between vertex 0 and vertex 3.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph is diamond-free if it contains no induced subgraph isomorphic to the diamond graph. -/ def is_diamond_free {V : Type*} (G : SimpleGraph V) : Prop := ¬ SimpleGraph.IsIndContained diamond_graph G