AFTD Auto-Formalizing Theoretical Domains

arrows_legal_move_degree_ne_one

theoremverified

If marking the unmarked edge uv as u -> v leaves u not a source and v not a sink, then neither u nor v has degree 1 (pendant edges can never be marked).

Statement

theorem arrows_legal_move_degree_ne_one {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {p q : ArrowsPos V} {u v : V}
    (hu : ArrowsUnmarked G p u v) (hq : ∀ x y, q.1 x y = if x = u ∧ y = v then true else p.1 x y)
    (hsu : ¬ ArrowsIsSource G q u) (hsv : ¬ ArrowsIsSink G q v) :
    G.degree u ≠ 1 ∧ G.degree v ≠ 1
Source
Helper for arrows_parity_of_threads_le_two, arXiv:2610.15145 Theorem 10.3 / Corollary 10.4 (the induction in the proof of Theorem 10.3: every option has value (e-1) mod 2 or an option of value e mod 2), done directly on positions of T without the sum decomposition
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • ArrowsUnmarkedIn a simple graph G and position p : ArrowsPos V, vertices u and v form an unmarked edge if G.Adj u v and both p.1 u v and p.1 v u are…
  • ArrowsIsSourceIn a simple graph G and position p : ArrowsPos V, vertex u is a source if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1…
  • ArrowsIsSinkIn a simple graph G and position p : ArrowsPos V, vertex u is a sink if G.degree u ≥ 1 and for every neighbor v adjacent to u in G, p.1 v…
  • ArrowsPosGiven a type V, ArrowsPos V is the subtype of boolean-valued binary relations p : V → V → Bool that are asymmetric, meaning that for all…
Used by 1

The proof, explained

The proof proceeds by contradiction for each vertex separately. Marking the edge uv as u → v establishes that the directed edge from u to v is present in q. If u had degree 1, its unique neighbor would be v, meaning every incident edge points away from u, so u would be a source, contradicting the assumption. Symmetrically, if v had degree 1, its unique neighbor would be u, so the only incident edge points into v, making v a sink and contradicting the assumption.

  1. In the updated orientation q, the directed edge from u to v is marked (q(u, v) = true).

    By the definition of q given in hypothesis hq, the edge between x and y is directed from x to y if x = u and y = v, which immediately simplifies to true when evaluated at (u, v).

    line 6

      have hquv : q.1 u v = true := by rw [hq]; simp
  2. It suffices to show G.degree u ≠ 1 and G.degree v ≠ 1 separately.

    The goal is a conjunction of two inequalities, which is split into two independent subgoals.

    line 7

      constructor
  3. G.degree u ≠ 1

    Suppose for contradiction that G.degree u = 1. We show that u must be a source in q, contradicting hypothesis hsu. A vertex with degree at least 1 is a source if all its incident edges are directed away from it. Since G.degree u = 1, its neighbor finset has cardinality 1 by SimpleGraph.card_neighborFinset_eq_degree, so by Finset.card_eq_one.mp this neighborhood is a singleton {a}. Because v is adjacent to u (from hu), v = a by Finset.mem_singleton. Any neighbor w of u must likewise satisfy w = a = v, so every outgoing edge from u is of the form (u, v). Since q(u, v) = true, every edge incident to u points away from u, making u a source and yielding the contradiction.

    lines 8–16

    uses Finset.card_eq_one.mp, SimpleGraph.card_neighborFinset_eq_degree, Finset.mem_singleton

      · intro h1
        apply hsu
        refine ⟨by omega, fun w hw => ?_⟩
        obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 :
          (G.neighborFinset u).card = 1)
        have hv : v ∈ G.neighborFinset u := by simpa using hu.1
        have hw' : w ∈ G.neighborFinset u := by simpa using hw
        rw [ha, Finset.mem_singleton] at hv hw'
        rw [hw', ← hv]; exact hquv
  4. G.degree v ≠ 1

    Suppose for contradiction that G.degree v = 1. We show that v must be a sink in q, contradicting hypothesis hsv. Symmetrically to the first case, G.degree v = 1 implies the neighbor finset of v has cardinality 1 by SimpleGraph.card_neighborFinset_eq_degree, so it is a singleton {a} by Finset.card_eq_one.mp. Since u is adjacent to v, u = a by Finset.mem_singleton. Thus any neighbor w of v satisfies w = u, meaning every edge incident to v is the edge from u to v. Since q(u, v) = true, every incident edge points into v, making v a sink and yielding the contradiction.

    lines 17–25

    uses Finset.card_eq_one.mp, SimpleGraph.card_neighborFinset_eq_degree, Finset.mem_singleton

      · intro h1
        apply hsv
        refine ⟨by omega, fun w hw => ?_⟩
        obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 :
          (G.neighborFinset v).card = 1)
        have hv : u ∈ G.neighborFinset v := by simpa using hu.1.symm
        have hw' : w ∈ G.neighborFinset v := by simpa using hw
        rw [ha, Finset.mem_singleton] at hv hw'
        rw [hw', ← hv]; exact hquv
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is equal to a singleton set {a} for some element a (used here in the forward direction: cardinality 1 implies it is a singleton).
SimpleGraph.card_neighborFinset_eq_degree
For any vertex v in a graph G, the cardinality of its neighbor finset equals the degree of v.
Finset.mem_singleton
An element b belongs to the singleton finset {a} if and only if b = a.

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

theorem arrows_legal_move_degree_ne_one {V : Type*} [DecidableEq V] [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] {p q : ArrowsPos V} {u v : V}    (hu : ArrowsUnmarked G p u v) (hq : ∀ x y, q.1 x y = if x = u ∧ y = v then true else p.1 x y)    (hsu : ¬ ArrowsIsSource G q u) (hsv : ¬ ArrowsIsSink G q v) :    G.degree u ≠ 1 ∧ G.degree v ≠ 1 := by  have hquv : q.1 u v = true := by rw [hq]; simp  constructor  · intro h1    apply hsu    refine ⟨by omega, fun w hw => ?_⟩    obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 :      (G.neighborFinset u).card = 1)    have hv : v ∈ G.neighborFinset u := by simpa using hu.1    have hw' : w ∈ G.neighborFinset u := by simpa using hw    rw [ha, Finset.mem_singleton] at hv hw'    rw [hw', ← hv]; exact hquv  · intro h1    apply hsv    refine ⟨by omega, fun w hw => ?_⟩    obtain ⟨a, ha⟩ := Finset.card_eq_one.mp (by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact h1 :      (G.neighborFinset v).card = 1)    have hv : u ∈ G.neighborFinset v := by simpa using hu.1.symm    have hw' : w ∈ G.neighborFinset v := by simpa using hw    rw [ha, Finset.mem_singleton] at hv hw'    rw [hw', ← hv]; exact hquv
See it in the graphDiscuss this resultChallenge it