AFTD Auto-Formalizing Theoretical Domains

is_mutual_visibility_set

def

A set S of vertices in a simple graph G is a mutual-visibility set if for every two distinct vertices u, v in S, there exists a shortest path between u and v whose internal vertices lie outside S.

Statement

def is_mutual_visibility_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
Defined in
arXiv:2611.09513, Section 1
Verified
09 Nov 2026
Axioms
none listed
Used by 2

Read back from the Lean

For a simple graph G on vertex type V and a subset S of V, is_mutual_visibility_set G S asserts that for all distinct vertices u, v ∈ S (with u ≠ v), there exists a walk p in G from u to v such that: 1. The length of p equals the graph distance between u and v (G.dist u v), meaning p is a shortest path (geodesic) between u and v. 2. Every vertex w in the support of p that belongs to S is either u or v (i.e., no intermediate vertex on p belongs to S).

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 set `S` of vertices in a simple graph `G` is a mutual-visibility set if every two distinct vertices in `S` have a shortest path with all internal vertices outside `S`. -/
def is_mutual_visibility_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ ⦃u v : V⦄, u ∈ S → v ∈ S → u ≠ v →
  ∃ p : G.Walk u v, p.length = G.dist u v ∧ ∀ w ∈ p.support, w ∈ S → w = u ∨ w = v
See it in the graphDiscuss this resultChallenge it