Lemma 2.2 (subset deficit): a minimal counterexample has positive indegrees and satisfies for every nonempty proper
ProvedOAI.SeymourSecondNeighborhood.lemma_2_2Let be a finite nonempty oriented graph on (a loopless asymmetric relation ) in which every vertex is bad, i.e. , where is the out-neighborhood and the set of vertices at directed distance exactly two. Assume is minimal in the following two senses: every proper subrelation (obtained by deleting at least one arc) has a good vertex, and every nonempty proper induced subgraph , , has a good vertex. Write for the one-step image (fwd). Then every vertex of has an in-neighbor, and
(SubsetDeficit). This is Lemma 2.2 of the manuscript, which adapts the arc-deletion argument of Seacrest's Lemma 4 (arXiv:1808.06293): for fixed, put , and for ; deleting the arcs from to and using arc-minimality produces a nonempty with , and iterating from to gives . The two minimality hypotheses are exactly what a counterexample of minimum order and then minimum number of arcs provides (the induced-subgraph hypothesis follows from the main theorem for smaller orders).
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
namespace OAI.SeymourSecondNeighborhood
variable {V : Type*} [Fintype V] [DecidableEq V]
theorem lemma_2_2 [Nonempty V] (r : V → V → Prop) (hr : IsOriented r)
(hbad : ∀ v, ¬ GoodVertex r v)
(hmin_arcs : ∀ r' : V → V → Prop, (∀ a b, r' a b → r a b) → (∃ a b, r a b ∧ ¬ r' a b) →
∃ v, GoodVertex r' v)
(hmin_order : ∀ W : Finset V, W.Nonempty → W ≠ univ →
∃ v : W, GoodVertex (fun a b : W => r a b) v) :
PosIndeg r ∧ SubsetDeficit r := by
sorry
end OAI.SeymourSecondNeighborhood