minor_edge_not_loop_of_all_none
Sanity check: if no edge has been queried (every edge is assigned weight none), then no edge of G is a loop in the minor G_β.
Statement
theorem minor_edge_not_loop_of_all_none {V : Type*} (G : SimpleGraph V) (e : G.edgeSet) : ¬ minor_edge_is_loop G (fun _ => none) e
- Source
- folklore
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- minor_edge_is_loopFor a simple graph G and a partial edge-weight realization β : G.edgeSet → Option Bool, an edge e of G is a loop in the minor G_β…
Read back from the Lean
For any type V, any simple graph G on V, and any edge e of G, minor_edge_is_loop G (fun _ => none) e does not hold, where fun _ => none is the edge-labeling function assigning none to every edge of G.
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
We argue by contradiction: if an edge $e = s(u, v)$ were a loop in the minor when no edges have been queried, $u$ and $v$ would be connected by a walk of contracted edges (edges assigned `some false`). By induction on this walk, a zero-step walk would imply $u = v$, meaning $e$ is a self-loop, which contradicts that $G$ is a simple graph. A walk with at least one step is also impossible, because the first step would require an edge assigned `some false`, contradicting that all edges are assigned `none`.
Assume for contradiction that $e$ is a loop in the minor, yielding endpoints $u, v$ with $e = s(u, v)$ connected by a walk $w$ of contracted edges.
We assume the negation of the goal, namely that $e$ is a loop in the minor when no edges are queried (the edge weighting function constantly returns `none`). Unfolding the definition of `minor_edge_is_loop`, this implies that $e$ joins vertices $u$ and $v$ that are reachable from one another in the graph formed by contracted edges (edges assigned `some false`). We extract these endpoints $u, v$, the equality $e = s(u, v)$, and a walk $w$ connecting them.
intro h unfold minor_edge_is_loop at h rcases h with ⟨u, v, he, ⟨w⟩⟩
The walk $w$ cannot be of length zero (`nil`), as that would force $e$ to be a self-loop in the simple graph $G$.
We induct on the walk $w$. In the base case where $w$ is the empty walk (`nil`), its start and end vertices coincide ($u = v$). Rewriting $e = s(u, u)$ shows that $e$ is a diagonal element of $\operatorname{Sym}^2(V)$ using `Sym2.mk_isDiag_iff.mpr`. However, $e$ is an edge of the simple graph $G$, and `G.not_mem_edgeSet_of_isDiag` states that simple graphs contain no diagonal edges (self-loops), yielding a contradiction.
uses
Sym2.mk_isDiag_iff.mpr,G.not_mem_edgeSet_of_isDiaginduction w with | nil => have hd : (e : Sym2 V).IsDiag := by rw [he] exact Sym2.mk_isDiag_iff.mpr rfl exact G.not_mem_edgeSet_of_isDiag hd e.2
The walk $w$ cannot have length at least one (`cons`), because no edges have been contracted.
In the inductive step where $w$ has at least one step (`cons`), the first step is an adjacency between some vertices in the graph of contracted edges. By `SimpleGraph.fromEdgeSet_adj`, this edge must belong to the set of contracted edges, which requires its weight under the constant-`none` function to equal `some false`. This equates `none` and `some false`, an immediate contradiction between distinct constructors of `Option`.
uses
SimpleGraph.fromEdgeSet_adj| cons hadj _ _ => rw [SimpleGraph.fromEdgeSet_adj] at hadj rcases hadj.1 with ⟨_, h_none⟩ contradiction
Sym2.mk_isDiag_iff.mpr- An unordered pair with identical elements $s(x, x)$ is a diagonal element (self-loop).
G.not_mem_edgeSet_of_isDiag- A simple graph has no diagonal edges (self-loops).
SimpleGraph.fromEdgeSet_adj- Two vertices are adjacent in a graph induced by an edge set if and only if they are distinct and the edge between them belongs to that set.
- In Lean's SimpleGraph library, reachability is defined via the existence of an explicit walk (`SimpleGraph.Walk u v`), allowing structural induction on the length of the walk.
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.
/-- Sanity check: when no edges are queried, no edge is a loop in the minor. -/theorem minor_edge_not_loop_of_all_none {V : Type*} (G : SimpleGraph V) (e : G.edgeSet) : ¬ minor_edge_is_loop G (fun _ => none) e := by intro h unfold minor_edge_is_loop at h rcases h with ⟨u, v, he, ⟨w⟩⟩ induction w with | nil => have hd : (e : Sym2 V).IsDiag := by rw [he] exact Sym2.mk_isDiag_iff.mpr rfl exact G.not_mem_edgeSet_of_isDiag hd e.2 | cons hadj _ _ => rw [SimpleGraph.fromEdgeSet_adj] at hadj rcases hadj.1 with ⟨_, h_none⟩ contradiction