is_mutual_visibility_set_empty
The empty set of vertices in any simple graph G is a mutual-visibility set.
Statement
theorem is_mutual_visibility_set_empty {V : Type*} (G : SimpleGraph V) : is_mutual_visibility_set G ∅
- Source
- arXiv:2611.09513, Section 1
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_mutual_visibility_setA 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…
- simple_graph_power_oneG^1 = G.
Read back from the Lean
For any type V and any simple graph G on V, the empty set ∅ is a mutual visibility set in G. That is, for all vertices u, v : V, if u ∈ ∅, v ∈ ∅, and u ≠ v, then there exists a walk p from u to v in G whose length is G.dist u v and such that every vertex w in the support of p that is in ∅ is equal to u or v.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The empty set of vertices in any simple graph is a mutual-visibility set because the condition is vacuously satisfied. By definition, a set of vertices is a mutual-visibility set if every pair of distinct vertices in it can see each other via a shortest path containing no other vertices from the set. Since the empty set contains no vertices, there are no pairs to consider, and the implication holds vacuously.
The empty set $\emptyset$ is a mutual-visibility set in $G$.
Unfolding the definition of `is_mutual_visibility_set` expresses the goal as a universal quantification over vertices $u, v \in V$: if $u \in \emptyset$, $v \in \emptyset$, and $u \ne v$, then there exists a distance-achieving walk whose internal vertices avoid $\emptyset$. Because no element belongs to the empty set, the hypothesis $u \in \emptyset$ simplifies to `False`, making the conditional statement vacuously true. The automated proof ladder tries several tactics and succeeds on the branch that unfolds the definition and simplifies this vacuous implication.
uses
is_mutual_visibility_set,simple_graph_power_oneis_mutual_visibility_set G ∅ := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_mutual_visibility_set] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)
is_mutual_visibility_set- A subset $S$ of vertices in a simple graph $G$ is a mutual-visibility set if for every pair of distinct vertices $u, v \in S$, there is a shortest path in $G$ between $u$ and $v$ whose internal vertices contain no elements of $S$.
simple_graph_power_one- The first power of a simple graph $G$ is identical to $G$.
- The proof script was generated by automated proof search and consists of an elaborate tactic fallback ladder (`first | ...`).
- The lemma `simple_graph_power_one` (stating that the first power of a graph is the graph itself) is mathematically irrelevant; `simpa` closes the goal entirely because the premise $u \in \emptyset$ simplifies to `False`, making the implication vacuously true.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty set is a mutual-visibility set. -/theorem is_mutual_visibility_set_empty {V : Type*} (G : SimpleGraph V) : is_mutual_visibility_set G ∅ := by first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one | (simp only [is_mutual_visibility_set] at *; first | exact simple_graph_power_one | (apply simple_graph_power_one <;> assumption) | (apply simple_graph_power_one <;> simp_all) | simpa using simple_graph_power_one)