AFTD Auto-Formalizing Theoretical Domains

is_ab_linked

def

A graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2 ⊇ M2, each inducing a connected subgraph.

Statement

def is_ab_linked {V : Type*} [DecidableEq V] (G : SimpleGraph V) (a b : ℕ) : Prop
Defined in
arXiv:1908.05433, Definition 3.8 ((a,b)-linked graphs)
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
Used by 3
  • poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
  • poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
  • poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…

Lean source view module on GitHub

/-- (a,b)-linkedness: any disjoint `M1`, `M2` of sizes `a`, `b` extend to disjoint connected vertex sets `S1 ⊇ M1`, `S2 ⊇ M2`. -/
def is_ab_linked {V : Type*} [DecidableEq V] (G : SimpleGraph V) (a b : ℕ) : Prop :=
  ∀ M1 M2 : Finset V, Disjoint M1 M2 → M1.card = a → M2.card = b →
    ∃ S1 S2 : Set V, Disjoint S1 S2 ∧ (↑M1 : Set V) ⊆ S1 ∧ (↑M2 : Set V) ⊆ S2 ∧
      is_connected_vertex_set G S1 ∧ is_connected_vertex_set G S2
See it in the graphDiscuss this resultChallenge it