graph_is_mutual_visibility_set
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
- graph_11_mutual_visibility_chromatic_number_eq_threeThe simple graph G_11 has mutual-visibility chromatic number 3, chromatic number 3, and diameter 2.
- graph_mutual_visibility_chromatic_number_le_chromatic_number_of_diam_twoFor every finite simple graph G of diameter 2, the mutual-visibility chromatic number of G is at most the chromatic number of G.
- graph_11_not_is_mutual_visibility_colorable_twoThe simple graph G_11 is not mutual-visibility 2-colorable.
- graph_is_mutual_visibility_colorableA simple graph G is mutual-visibility n-colorable if there exists a coloring of the vertices of G with n colors such that every color…
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