cycle_alternating_path_selection_independent
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
- alternating_path_selected_setFor a simple graph C on vertex type V, a vertex ρ : V, and subsets A and T of the subtype {ρ}ᶜ, alternating_path_selected_set C ρ A T is…
- alternating_path_selected_subset_b_indepIf the induced graph C[{ρ}ᶜ] is bipartite with parts A and B, then any subset T ⊆ B is an independent set in C[{ρ}ᶜ].
- Used by 1
- cycle_alternating_path_selection_isIndepSetLet 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…
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.
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.
uses
alternating_path_selected_set,Set.mem_union,Set.mem_ofPred_eq,SimpleGraph.induce_adj.mprintro 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
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).
uses
alternating_path_selected_subset_b_indeprcases 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
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.
· rcases hv with hvT | ⟨hvA, hvP⟩ · exact huP v hvT hG
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.
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.
- Vertices in the induced subgraph on {ρ}ᶜ are represented as subtype elements, so adjacency in C and adjacency in the induced subgraph are formally related via SimpleGraph.induce_adj.mpr.
- The expression Set.disjoint_left.1 uses dot notation for Set.disjoint_left.mp, extracting the forward direction of the equivalence defining disjoint sets.
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 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