AFTD Auto-Formalizing Theoretical Domains

has_asteroidal_triple_nonpaths

def

A graph H contains an asteroidal triple of nonpaths if there exist three pairwise disjoint, pairwise antiadjacent subsets of vertices, each inducing a connected subgraph that is not a path graph, such that for every pair there is a path connecting them that avoids the closed neighborhood of the third.

Statement

def has_asteroidal_triple_nonpaths {V : Type*} (H : SimpleGraph V) : Prop
Defined in
arXiv:2611.09627:403
Verified
09 Nov 2026
Axioms
none listed
Built on 2
  • is_path_graphA simple graph is a path graph if it is isomorphic to a standard path graph on n vertices for some n.
  • closed_neighbor_setThe closed neighborhood of a vertex set A in a graph G is the set of all vertices in A together with all vertices adjacent to at least one…

Read back from the Lean

For a simple graph $H$ on a type $V$, has_asteroidal_triple_nonpaths H asserts that there exist three subsets $A_1, A_2, A_3 \subseteq V$ such that: 1. $A_1, A_2, A_3$ are pairwise disjoint ($A_1 \cap A_2 = \emptyset$, $A_1 \cap A_3 = \emptyset$, and $A_2 \cap A_3 = \emptyset$). 2. There are no edges in $H$ between any two of the sets: - For all $u \in A_1$ and $v \in A_2$, $u$ and $v$ are not adjacent in $H$. - For all $u \in A_1$ and $v \in A_3$, $u$ and $v$ are not adjacent in $H$. - For all $u \in A_2$ and $v \in A_3$, $u$ and $v$ are not adjacent in $H$. 3. For each $i \in \{1, 2, 3\}$, the induced subgraph $H[A_i]$ is connected and is not isomorphic to any finite path graph SimpleGraph.pathGraph n (for any $n \in \mathbb{N}$). 4. Between every pair of sets among $\{A_1, A_2, A_3\}$, there exists a walk in $H$ connecting a vertex of the first set to a vertex of the second set whose vertices avoid the closed neighborhood of the third set: - There exist $u \in A_1$, $v \in A_2$, and a walk $p$ in $H$ from $u$ to $v$ such that no vertex in the support of $p$ belongs to the closed neighborhood of $A_3$ (i.e., no vertex of $p$ is in $A_3$ or adjacent to any vertex of $A_3$). - There exist $u \in A_1$, $v \in A_3$, and a walk $p$ in $H$ from $u$ to $v$ such that no vertex in the support of $p$ belongs to the closed neighborhood of $A_2$. - There exist $u \in A_2$, $v \in A_3$, and a walk $p$ in $H$ from $u$ to $v$ such that no vertex in the support of $p$ belongs to the closed neighborhood of $A_1$.

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 graph H has an asteroidal triple of nonpaths if it contains three pairwise disjoint, pairwise antiadjacent connected vertex sets, none of which induces a path graph, such that any two can be joined by a walk in H avoiding the closed neighborhood of the third. -/
def has_asteroidal_triple_nonpaths {V : Type*} (H : SimpleGraph V) : Prop := ∃ (A₁ A₂ A₃ : Set V),
    Disjoint A₁ A₂ ∧ Disjoint A₁ A₃ ∧ Disjoint A₂ A₃ ∧
    (∀ u ∈ A₁, ∀ v ∈ A₂, ¬ H.Adj u v) ∧
    (∀ u ∈ A₁, ∀ v ∈ A₃, ¬ H.Adj u v) ∧
    (∀ u ∈ A₂, ∀ v ∈ A₃, ¬ H.Adj u v) ∧
    (H.induce A₁).Connected ∧ ¬ is_path_graph (H.induce A₁) ∧
    (H.induce A₂).Connected ∧ ¬ is_path_graph (H.induce A₂) ∧
    (H.induce A₃).Connected ∧ ¬ is_path_graph (H.induce A₃) ∧
    (∃ u ∈ A₁, ∃ v ∈ A₂, ∃ p : H.Walk u v, ∀ x ∈ p.support, x ∉ closed_neighbor_set H A₃) ∧
    (∃ u ∈ A₁, ∃ v ∈ A₃, ∃ p : H.Walk u v, ∀ x ∈ p.support, x ∉ closed_neighbor_set H A₂) ∧
    (∃ u ∈ A₂, ∃ v ∈ A₃, ∃ p : H.Walk u v, ∀ x ∈ p.support, x ∉ closed_neighbor_set H A₁)
See it in the graphDiscuss this resultChallenge it