is_mutual_visibility_set
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
- is_mutual_visibility_set_emptyThe empty set of vertices in any simple graph G is a mutual-visibility set.
- mutual_visibility_numberThe mutual-visibility number of a finite graph G is the maximum size of a mutual-visibility set of vertices in G.
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