digraph_two_vertex_avoidance_obstruction_parent_adjacency
theoremverified
If every quasi-kernel of a finite loopless digraph contains at least one of two specified vertices, then each in-neighbor of the first vertex is distinct from and adjacent to each in-neighbor of the second.
Statement
theorem digraph_two_vertex_avoidance_obstruction_parent_adjacency {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (a b x y : α) (hloop : ∀ v, ¬ D.Adj v v) (hblocked : ∀ Q : Finset α, (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) → (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) → a ∈ Q ∨ b ∈ Q) (hxa : D.Adj x a) (hyb : D.Adj y b) : x ≠ y ∧ (D.Adj x y ∨ D.Adj y x)
- Source
- Consequence of the independent-neighborhood avoidance construction in OP-337.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_quasikernel_independent_cover_avoids_outneighborsIn a finite loopless digraph, every independent set is contained in the closed out-neighborhood of a quasi-kernel that contains none of…
Lean source view module on GitHub
theorem digraph_two_vertex_avoidance_obstruction_parent_adjacency {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (a b x y : α) (hloop : ∀ v, ¬ D.Adj v v) (hblocked : ∀ Q : Finset α, (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → ¬ D.Adj u v) → (∀ v, ∃ u ∈ Q, u = v ∨ D.Adj u v ∨ ∃ w, D.Adj u w ∧ D.Adj w v) → a ∈ Q ∨ b ∈ Q) (hxa : D.Adj x a) (hyb : D.Adj y b) : x ≠ y ∧ (D.Adj x y ∨ D.Adj y x) := by classical by_contra h have hne : x ≠ y → ¬ D.Adj x y ∧ ¬ D.Adj y x := by intro hxy constructor · intro h1 exact h ⟨hxy,Or.inl h1⟩ · intro h1 exact h ⟨hxy,Or.inr h1⟩ have hind : ∀ u ∈ ({x,y} : Finset α), ∀ v ∈ ({x,y} : Finset α), u ≠ v → ¬ D.Adj u v := by intro u hu v hv huv hadj simp only [Finset.mem_insert,Finset.mem_singleton] at hu hv rcases hu with rfl | rfl <;> rcases hv with rfl | rfl · exact (huv rfl).elim · exact (hne huv).1 hadj · exact (hne (Ne.symm huv)).2 hadj · exact (huv rfl).elim obtain ⟨Q,hQind,hQcov,_,havoid⟩ := digraph_quasikernel_independent_cover_avoids_outneighbors D {x,y} hind hloop rcases hblocked Q hQind hQcov with ha | hb · exact havoid a ha ⟨x,by simp,hxa⟩ · exact havoid b hb ⟨y,by simp,hyb⟩