AFTD Auto-Formalizing Theoretical Domains

graph_is_mutual_visibility_set

def

A set S of vertices of a simple graph G is a mutual-visibility set if for every pair of vertices u, v in S, there exists a shortest walk from u to v in G such that every vertex on the walk that belongs to S is either u or v.

Statement

def graph_is_mutual_visibility_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop
Defined in
arXiv:2610.39430, Definition 1.1
Verified
30 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

For a simple graph G on a type V and a set of vertices S : Set V, graph_is_mutual_visibility_set G S asserts that for every u ∈ S and every v ∈ S, there exists a walk p in G from u to v such that: 1. The length of p equals the graph distance G.dist u v (i.e., p is a shortest walk/geodesic between u and v), and 2. For every vertex x visited by p (i.e., x ∈ p.support), if x ∈ S, then x = u or x = v (i.e., no internal vertex of 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 of G is a mutual-visibility set if every pair in S is joined by a shortest walk whose internal vertices avoid S. -/
def graph_is_mutual_visibility_set {V : Type*} (G : SimpleGraph V) (S : Set V) : Prop := ∀ u ∈ S, ∀ v ∈ S, ∃ p : G.Walk u v, p.length = G.dist u v ∧
    ∀ x ∈ p.support, x ∈ S → x = u ∨ x = v
See it in the graphDiscuss this resultChallenge it