AFTD Auto-Formalizing Theoretical Domains

cycle_alternating_path_selection_independent

theoremverifiedformalization

Let C be a simple graph on vertex type V and ρ : V a vertex such that (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B holds for subsets A, B of the subtype {ρ}ᶜ. For any subset T ⊆ B, every pair of vertices u, v in alternating_path_selected_set C ρ A T satisfies ¬ C.Adj u v.

Statement

theorem cycle_alternating_path_selection_independent {V : Type*} (C : SimpleGraph V) (ρ : V)
    (A B : Set ({ρ}ᶜ : Set V))
    (h_bip : (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B)
    (T : Set ({ρ}ᶜ : Set V)) (hT : T ⊆ B) :
    ∀ u ∈ alternating_path_selected_set C ρ A T,
    ∀ v ∈ alternating_path_selected_set C ρ A T,
    ¬ C.Adj u v
Formalizes
arXiv:2611.06985 Lemma 3.3 -- Every r-regular Hamiltonian graph with r >= 17 contains a second Hamilton cycle
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

Read back from the Lean

For any type V, any simple graph C on V, and any vertex ρ : V: Suppose A and B are sets of vertices in the subtype {ρ}ᶜ (i.e., vertices of V distinct from ρ) such that the induced subgraph of C on {ρ}ᶜ is bipartite with parts A and B ((C.induce {ρ}ᶜ).IsBipartiteWith A B). Suppose T is a subset of {ρ}ᶜ satisfying T ⊆ B. Then for every u in alternating_path_selected_set C ρ A T and every v in alternating_path_selected_set C ρ A T, u and v (coerced to vertices in V) are not adjacent in C (¬ C.Adj u v). In other words, the set alternating_path_selected_set C ρ A T is an independent set in C.

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 proof establishes that the alternating path selected set S = T ∪ {a ∈ A | ∀ b ∈ T, ¬ Adj(a, b)} is an independent set in C by contradiction and case analysis. Assuming two vertices u, v ∈ S are adjacent in C, they must also be adjacent in the induced subgraph C[{ρ}ᶜ]. The four cases for the membership of u and v in T versus A are each ruled out: two vertices in T cannot be adjacent because T ⊆ B is independent; a vertex in T and a vertex in A cannot be adjacent by the non-adjacency condition in the definition of S; and two vertices in A cannot be adjacent because C[{ρ}ᶜ] is bipartite with disjoint parts A and B.

  1. Suppose for contradiction that two vertices u, v in the alternating path selected set are adjacent in C; then they are also adjacent in the induced subgraph on {ρ}ᶜ.

    We fix u and v in alternating_path_selected_set C ρ A T. Unfolding the definition of the set, each of u and v either belongs to T, or belongs to A and has no neighbors in T within the induced subgraph. We then assume for contradiction that u and v are adjacent in C (hadj). Since u and v are vertices in the complement {ρ}ᶜ, their adjacency in C implies adjacency in the induced subgraph C[{ρ}ᶜ] by SimpleGraph.induce_adj.mpr.

    lines 9–12

    uses alternating_path_selected_set, Set.mem_union, Set.mem_ofPred_eq, SimpleGraph.induce_adj.mpr

      intro u hu v hv
      simp only [alternating_path_selected_set, Set.mem_union, Set.mem_ofPred_eq] at hu hv
      rintro hadj
      have hG : (C.induce ({ρ}ᶜ : Set V)).Adj u v := SimpleGraph.induce_adj.mpr hadj
  2. If u ∈ T, then u cannot be adjacent to v.

    We split on whether u ∈ T or u ∈ A. In the case u ∈ T, we further split on whether v ∈ T or v ∈ A. If v ∈ T, both u and v belong to T ⊆ B, but T is an independent set in the induced bipartite subgraph by alternating_path_selected_subset_b_indep, contradicting adjacency. If v ∈ A, then by definition of the selected set, v has no neighbors in T; since u ∈ T, this contradicts adjacency between u and v (by symmetry of adjacency).

    lines 13–16

    uses alternating_path_selected_subset_b_indep

      rcases hu with huT | ⟨huA, huP⟩
      · rcases hv with hvT | ⟨hvA, hvP⟩
        · exact alternating_path_selected_subset_b_indep C ρ A B h_bip T hT u huT v hvT hG
        · exact hvP u huT hG.symm
  3. If u ∈ A and v ∈ T, then u cannot be adjacent to v.

    In the case u ∈ A, the definition of the selected set ensures that u has no induced neighbors in T. Thus, if v ∈ T, the adjacency between u and v is immediately a contradiction.

    lines 17–18

      · rcases hv with hvT | ⟨hvA, hvP⟩
        · exact huP v hvT hG
  4. If both u ∈ A and v ∈ A, then u cannot be adjacent to v.

    In the final case where both u ∈ A and v ∈ A, bipartiteness of the induced subgraph implies that the edge between u and v must connect an element of A to an element of B (h_bip.mem_of_adj). Hence either v ∈ B or u ∈ B. But A and B are disjoint sets (h_bip.disjoint), so an element of A cannot also be in B (Set.disjoint_left.1), giving a contradiction in both branches.

    lines 19–21

    uses h_bip.mem_of_adj, h_bip.disjoint, Set.disjoint_left.1

        · rcases h_bip.mem_of_adj hG with ⟨_, hvB⟩ | ⟨huB, _⟩
          · exact (Set.disjoint_left.1 h_bip.disjoint) hvA hvB
          · exact (Set.disjoint_left.1 h_bip.disjoint) huA huB
alternating_path_selected_set
The definition of the alternating path selected set: T ∪ {a ∈ A | ∀ b ∈ T, ¬ Adj(a, b)}.
Set.mem_union
An element belongs to the union a ∪ b if and only if it belongs to a or to b.
Set.mem_ofPred_eq
Membership in a set comprehension {y | p y} is equivalent to p holding for that element.
SimpleGraph.induce_adj.mpr
If two vertices of an induced subgraph are adjacent in the original graph, they are adjacent in the induced subgraph.
alternating_path_selected_subset_b_indep
Any subset T of the part B is an independent set in the induced bipartite subgraph.
h_bip.mem_of_adj
In a bipartite graph with parts A and B, any edge has one endpoint in A and the other in B.
h_bip.disjoint
The two parts A and B of a bipartite graph are disjoint.
Set.disjoint_left.1
If two sets are disjoint, an element of the first set cannot belong to the second 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

/-- The alternating path selected set S is independent in the cycle graph C. -/theorem cycle_alternating_path_selection_independent {V : Type*} (C : SimpleGraph V) (ρ : V)    (A B : Set ({ρ}ᶜ : Set V))    (h_bip : (C.induce ({ρ}ᶜ : Set V)).IsBipartiteWith A B)    (T : Set ({ρ}ᶜ : Set V)) (hT : T ⊆ B) :    ∀ u ∈ alternating_path_selected_set C ρ A T,    ∀ v ∈ alternating_path_selected_set C ρ A T,    ¬ C.Adj u v := by  intro u hu v hv  simp only [alternating_path_selected_set, Set.mem_union, Set.mem_ofPred_eq] at hu hv  rintro hadj  have hG : (C.induce ({ρ}ᶜ : Set V)).Adj u v := SimpleGraph.induce_adj.mpr hadj  rcases hu with huT | ⟨huA, huP⟩  · rcases hv with hvT | ⟨hvA, hvP⟩    · exact alternating_path_selected_subset_b_indep C ρ A B h_bip T hT u huT v hvT hG    · exact hvP u huT hG.symm  · rcases hv with hvT | ⟨hvA, hvP⟩    · exact huP v hvT hG    · rcases h_bip.mem_of_adj hG with ⟨_, hvB⟩ | ⟨huB, _⟩      · exact (Set.disjoint_left.1 h_bip.disjoint) hvA hvB      · exact (Set.disjoint_left.1 h_bip.disjoint) huA huB
See it in the graphDiscuss this resultChallenge it