has_asteroidal_triple_nonpaths
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₁)