AFTD Auto-Formalizing Theoretical Domains

minor_edge_not_loop_of_all_none

theoremverified

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`.

  1. 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.

    lines 4–6

      intro h
      unfold minor_edge_is_loop at h
      rcases h with ⟨u, v, he, ⟨w⟩⟩
  2. 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.

    lines 7–12

    uses Sym2.mk_isDiag_iff.mpr, G.not_mem_edgeSet_of_isDiag

      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
  3. 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`.

    lines 13–16

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it