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